Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure with constant space.
Example 1:
Input: [1,3,null,null,2]
1
/
3
\
2
Output: [3,1,null,null,2]
3
/
1
\
2
Example 2:
Input: [3,1,4,null,null,2]
3
/ \
1 4
/
2
Output: [2,1,4,null,null,3]
2
/ \
1 4
/
3
A solution using O(n) space is pretty straight forward using stack. but we need to achieve it with constant space.
Also we know that in-order traversal of BST is sorted output. So while doing in-order traversal, we should find 2 nodes, which need to be swapped to get the sorted output.
With Morris Traversal, we can achieve in-order traversal with constant memory
public void RecoverTree(TreeNode root) { TreeNode prev = null; TreeNode first = null, next = null; TreeNode current = root; while (current != null) { if (prev != null && current != null && prev.val > current.val) { if (first == null) { first = prev; next = current; } else { next = current; } } //left is null then print the node and go to right if (current.left == null) { //update previous pointer prev = current; Console.Write(current.val + " "); current = current.right; } else { //find the predecessor. TreeNode predecessor = current.left; //To find predecessor keep going right till right node is not null or right node is not current. while (predecessor.right != current && predecessor.right != null) { predecessor = predecessor.right; } //if right node is null then go left after establishing link from predecessor to current. if (predecessor.right == null) { predecessor.right = current; current = current.left; } else { //left is already visit. Go rigth after visiting current. predecessor.right = null; Console.Write(current.val + " "); //update previous pointer prev = current; current = current.right; } } } //Swap values if(first!=null && next !=null) { int temp = first.val; first.val = next.val; next.val = temp; } }