# 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.

Note:
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: