LeetCode Recover Binary Search Tree (java)

Tags: , ,

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Java Solution

We can use a stack to do an in order traverse of the tree, as it can produce a sorted list of a binary search tree. In the process, we keep track of two pointers pre, cur:

If we encounter pre.val > cur.val the first time, we get the first error node p1 = pre, and the potential second error node p2 = cur.

If we encounter pre.val > cur.val the second time, we get the second error node p2 = cur.

Finally, we exchange the value of p1 and p2 to recover the binary tree.

The above solution uses O(n) space. To get a O(1) space solution, we can use the idea of morris traverse or  Threaded binary tree to do an inorder Tree Traversal without recursion and without stack.

See the following code for the O(1) space solution: