LeetCode Q99: Recover Binary Search Tree (hard)

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?

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

The difficulties of this problem come from the requirement of using O(1) space only. With this requirement, methods based on recursion will not fit. Since the stack used during recursion will take O(n) spaces.

However, just reference of myself. I present the first solution which is based on recursion here.

Solution 1:

The idea of this solution is to traverse the tree using in-order traversal. Check whether nodes visited is in a ascending order. When a node violate the property, we need to save current node and a node just visited before it. Because we so far don't know which node violate the property unless both two violations are detected. It is possible that there is only one violation detected which means the violation happened just between father and son nodes we just recorded.  When there are two violations, we swap the max node of first pair with the min node of the second pair. Done!

Solution 2:

The idea is the same as solution 1. The difference here is to use threaded binary search tree, specifically, Morris traversal, which require O(1) space only and can still be finished in O(n) time. For more details of Morris traversal please see this post.