Recover Binary Search Tree

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?

O(n) space solution is to do an inorder traversal and find out the elements which are not increasing.

O(1) space solution: Two scenarios:

• [1,5,3,4,2,6] - swapped nodes aren't together
• [1,2,3,5,4,6] - swapped nodes are together

Since in-order traversal for bst is monotone, we can use in-order traversal along with previous visited node and swapped nodes to solve the problem If previous node value is greater than the current visited, we find the first swapped nodes. If later on we find a second node whose value is less than the previous node value, we find the second swapped node, otherwise the swapped nodes are together.

public void recoverTree(TreeNode root) {
        TreeNode[] swapped = new TreeNode[2];
        recoverTree(new TreeNode[1], swapped, root);
        if (swapped[0]!=null&&swapped[1]!=null) {
            swap(swapped[0], swapped[1]);
        }    
    }   

    public void recoverTree(TreeNode[] previous, TreeNode[] swapped, TreeNode root) {
        if (root==null) {
            return;
        }
        recoverTree(previous, swapped, root.left);
        if (previous[0]!=null && previous[0].val>root.val) {
            if (swapped[0]==null) {
                swapped[0] = previous[0];
            }
            swapped[1] = root;
        }
        previous[0] = root;
        recoverTree(previous, swapped, root.right);
    }

    private void swap(TreeNode t1, TreeNode t2) {
        int value = t1.val;
        t1.val = t2.val;
        t2.val = value;
    }