Recover Binary Search Tree

Problem

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. (link)

Example 1:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2:

Input: root = [3,1,4,null,null,2]
Output: [2,1,4,null,null,3]
Explanation: 2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints:

• The number of nodes in the tree is in the range [2, 1000].

• -231 <= Node.val <= 231 - 1

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Solution

Brute Force Approach

The inorder traversal of a valid BST produces values in sorted order. Since two node values are swapped, the current inorder traversal is not sorted, but it still contains all the correct values.

1. Traverse the tree inorder and store all values in a list.

2. Sort the list.

3. Traverse the tree inorder again and overwrite each node’s value with the corresponding sorted value. The tree structure remains unchanged; only the node values are corrected.

Time: O(n log n)

Space: O(n) for the list and O(h) recursion stack

class Solution {

    private void inorder(TreeNode root, List<Integer> order){

        if(root == null) return;

        inorder(root.left, order);
        order.add(root.val);
        inorder(root.right, order);
    }

    private void buildTree(TreeNode root, List<Integer> order, int[] i){
        if(root == null) return;

        buildTree(root.left, order, i);
        root.val = order.get(i[0]);
        i[0]+=1;
        buildTree(root.right, order, i);
    }

    public void recoverTree(TreeNode root) {
        List<Integer> order = new ArrayList<>();
        inorder(root, order);
        order.sort((a,b) -> Integer.compare(a,b));
        buildTree(root, order, new int[]{0});
    }
}

Optimal Approach

Key idea

A binary search tree (BST) visits its values in sorted order during an inorder traversal: left → node → right.

If exactly two node values were swapped, the inorder sequence is almost sorted. Find where it decreases, then swap the misplaced values back.

Find the misplaced nodes

A violation occurs when prev.val > current.val.

• Adjacent swapped values: one violation. Store first = prev and middle = current.

• Non-adjacent swapped values: two violations. Store first = prev at the first violation and last = current at the second.

Examples:

Adjacent: 1, 3, 2, 4 → one violation: 3 > 2 
Non-adjacent: 1, 5, 3, 4, 2, 6 → violations: 5 > 3 and 4 > 2

For an adjacent swap, swap first and middle.

For a non-adjacent swap, swap first and last.

Time - O(n)

Space - O(1) + O(h) - stack space

class Solution {
    TreeNode prev;
    TreeNode first; 
    TreeNode middle;
    TreeNode last;

    private void inorder(TreeNode root){

        if(root == null){
            return;
        }

        inorder(root.left);

        if(prev!=null && prev.val > root.val){
            if(first == null){
                first = prev;
                middle = root;
            }
            else{
                last = root;
            }
        }

        prev = root;

        inorder(root.right);
    }

    public void recoverTree(TreeNode root) {

        inorder(root);
        correctTree(first, middle, last);
    }

    private void correctTree(TreeNode first, 
    TreeNode middle, TreeNode last){
        if(last!=null){
            swap(first, last);
        }
        else if (middle!=null){
            swap(first, middle);
        }
    }

    private void swap(TreeNode a, TreeNode b){
        int temp = a.val;
        a.val = b.val;
        b.val = temp;
    }    
}