Leetcode 99 – Recover Binary Search Tree – Constant space

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;
        }
    }