Recover Binary Search Tree

Problem

Two nodes in a BST are swapped. Recover the tree without changing its structure.

Key insight: In-order traversal of a valid BST gives a sorted sequence. Two violations reveal the swapped nodes:

First violation: prev > curr → first = prev
Second violation (if any): second = curr

Approach — Morris Traversal (O(1) space) or recursive

Solutions

// C++ — recursive O(h) space
TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    if (prev && prev->val > node->val) {
        if (!first) first = prev;
        second = node;
    }
    prev = node;
    inorder(node->right);
}
void recoverTree(TreeNode* root) {
    inorder(root);
    swap(first->val, second->val);
}

// Java
TreeNode first = null, second = null, prev = null;
public void recoverTree(TreeNode root) {
    inorder(root);
    int tmp = first.val; first.val = second.val; second.val = tmp;
}
void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    if (prev != null && prev.val > node.val) {
        if (first == null) first = prev;
        second = node;
    }
    prev = node;
    inorder(node.right);
}

// JavaScript
function recoverTree(root) {
    let first = null, second = null, prev = null;
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        if (prev && prev.val > node.val) {
            if (!first) first = prev;
            second = node;
        }
        prev = node;
        inorder(node.right);
    }
    inorder(root);
    [first.val, second.val] = [second.val, first.val];
}

# Python
def recoverTree(root):
    first = second = prev = None

    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev
            second = node
        prev = node
        inorder(node.right)

    inorder(root)
    first.val, second.val = second.val, first.val

Complexity

Time: O(n)
Space: O(h), O(1) with Morris traversal

Key Insight

Adjacent swap: one violation (swap fix = first, node). Non-adjacent swap: two violations. second always updated on each violation found.