Recover Binary Search Tree

Master this topic with zero to advance depth.

Recover Binary Search Tree

Swapped nodes fix.

Hard

Approach 1

Level I: Inorder to Array (Identify Swaps)

Intuition

In a sorted array, the elements are always in increasing order. If two elements are swapped, we will find either one or two points where arr[i] > arr[i+1].

Thought Process

Perform inorder traversal to get all values.
In the sorted values, find the two values that are out of place.
Traverse the tree again and swap these two values back.

⏱ O(N)💾 O(N)

Detailed Dry Run

Tree Inorder	Swapped Pairs	First Node	Second Node
[1, 3, 2, 4]	(3, 2)	3	2
[3, 2, 1]	(3, 2), (2, 1)	3	1

java

public class Main {
    public void recoverTree(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        inorder(root, list);
        TreeNode first = null, second = null;
        for (int i = 0; i < list.size() - 1; i++) {
            if (list.get(i).val > list.get(i + 1).val) {
                if (first == null) first = list.get(i);
                second = list.get(i + 1);
            }
        }
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
    private void inorder(TreeNode root, List<TreeNode> list) {
        if (root == null) return;
        inorder(root.left, list);
        list.add(root);
        inorder(root.right, list);
    }
}

Approach 2

Level II: Iterative Inorder (Stack)

Intuition

Instead of checking sortedness in an array, we can do it on the fly using a stack during an iterative inorder traversal. We maintain a prev pointer and identify where prev.val > current.val.

Logic

Use a stack to perform inorder traversal.
Whenever prev.val > current.val, identifying the first and last out-of-order nodes.
Swap values of first and second.

⏱ O(N)💾 O(H)

Detailed Dry Run

Stack: [1, 3, 2]. Pop 3, prev=3. Pop 2, current=2. prev > current! first=3, second=2. Result: swap(3, 2).

java

public class Main {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null;
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) { stack.push(root); root = root.left; }
            root = stack.pop();
            if (prev != null && prev.val > root.val) {
                if (first == null) first = prev;
                second = root;
            }
            prev = root;
            root = root.right;
        }
        int tmp = first.val; first.val = second.val; second.val = tmp;
    }
}

Approach 3

Level III: Optimal (In-place Inorder)

Intuition

Thought Process

We can find the swapped nodes during a single inorder traversal without storing the whole tree. We keep tracks of the prev node seen. If prev.val > current.val, we have found an anomaly.

There are two cases:

Adjacent swaps: Only one anomaly point.
Non-adjacent swaps: Two anomaly points (first anomaly's prev and second anomaly's current).

Complexity

Time: $O(N)$
Space: $O(H)$ (Recursive stack)

⏱ O(N)💾 O(H)

Detailed Dry Run

Prev	Current	Anomaly?	First	Second
3	2	Yes (3>2)	3	2
2	1	Yes (2>1)	(keep 3)	1

java

public class Main {
    TreeNode first = null, second = null, prev = null;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null && prev.val > root.val) {
            if (first == null) first = prev;
            second = root;
        }
        prev = root;
        inorder(root.right);
    }
}

⚠️ Common Pitfalls & Tips

You must update second in every anomaly found. In Case 2 (non-adjacent swaps), second will be updated twice, correctly identifying the further node.

← Previous QuestionBinary Tree Maximum Path Sum

Next Question →Count Univalue Subtrees

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.