Leetcode OJ: Recover Binary Search Tree

Recover Binary Search Tree

 

Two elements of a binary search tree (BST) are swapped by mistake.
Recover the tree without changing its structure. 

An O(n) space algorithm is straight-forward. One can write the in-order traversal of the BST to a linear array, then find the two swapped elements and swap them back.

A better solution is to not explicitly write the in-order traversal to an array. In fact, we can just do an in-order traversal on the BST itself and find the swapped elements in the process. Notice that if we exchange two adjacent (in terms of in-order) nodes, then the logic to find swapped elements is a little different, but this is handled subtly in the code.


However, since the previous solution uses recursion, then the worst case space complexity is the depth of the tree, which could be as bad as O(n).

A tree O(1) space solution requires the used of Threaded Binary Tree, which I learned from other's solution. A threaded binary tree allows one to truly traverse a binary tree with constant space. In our case, we want a forward traversal, so the right child of any node who doesn't have a right child points to its in-order successor. Since we want to preserve the structure, we make that pointing on the fly and recover it after that pointing after use. A threaded binary tree solution is as follows. Notice that we need to find the in-order predecessor of each node twice. The total complexity of finding in-order predecessor of all nodes is O(n), since it's easy to see that every edge is traversed only once. So it is not too bad.