99. Recover Binary Search Tree

Tree Depth-First Search Binary Search Tree

Time: O(n)

Space: O(h)

Intuition

Exactly two nodes are swapped. An in-order traversal of a BST yields a sorted sequence, so the swap creates at most two "inversions" (positions where arr[i] > arr[i+1]). The first swapped node is at the first inversion's larger value; the second is at the last inversion's smaller value.

Algorithm

1In-order traversal, tracking prev node.
2If prev.val > curr.val: if first is null, set first=prev. Set second=curr (always update second).
3After traversal: swap first.val and second.val.

Example Walkthrough

Input: BST with 3 and 1 swapped: [3,1,4,null,null,2]

1.In-order visits: 1, 3, 2, 4.
2.At (3->2): inversion. first=3, second=2.
3.At (2->next visits correctly). Swap 3.val and 2.val.

Output: Corrected BST

Common Pitfalls

•There may be one or two inversions. Using a single in-order pass and always updating second captures both cases.

99.cs

// Approach: In a valid BST, inorder traversal produces a strictly increasing sequence.
// Exactly two nodes are swapped, causing at most two inversions (positions where prev > current).
// Track the 'previous' node visited during inorder traversal.
// At the first inversion: record previous as 'first' (misplaced larger node) and current as 'second'.
// At the second inversion (if it exists): update 'second' to the current node.
// After the full traversal, swap the values of 'first' and 'second' to fix the BST.
// Time: O(n) Space: O(h) for the recursion stack.

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
public class Solution
{
    private TreeNode first;
    private TreeNode prev;
    private TreeNode middle;
    private TreeNode last;
    public void RecoverTree(TreeNode root)
    {
        first = middle = last = null;
        prev = new TreeNode(Int32.MinValue);
        IOTRecoverTree(root);

        if (first != null && last != null)
        {
            int t = first.val;
            first.val = last.val;
            last.val = t;
        }
        else if (first != null && middle != null)
        {
            int t = first.val;
            first.val = middle.val;
            middle.val = t;
        }
    }

    private void IOTRecoverTree(TreeNode root)
    {
        if (root == null)
            return;

        IOTRecoverTree(root.left);

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

        prev = root;
        IOTRecoverTree(root.right);
    }
}

Was this solution helpful?