Recover Binary Search Tree

medium tree bst dfs

Problem

Exactly two values in a BST have been swapped by mistake. Recover the tree without changing its structure.

Inputroot = [3, 1, 4, null, null, 2]

Output[2, 1, 4, null, null, 3]

Inorder = [1, 3, 4, 2] → not sorted. The first descent is 3 → 4? No, 4 → 2; mark 4 as first and 2 as second. Swap them to get [1, 2, 3, 4].

level-order (use "null" for missing)

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

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

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

class Solution {
public:
    TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
    void inorder(TreeNode* n) {
        if (!n) return;
        inorder(n->left);
        if (prev && prev->val > n->val) {
            if (!first) first = prev;
            second = n;
        }
        prev = n;
        inorder(n->right);
    }
    void recoverTree(TreeNode* root) { inorder(root); swap(first->val, second->val); }
};

Explanation

The key fact about a BST is that an inorder traversal (left, node, right) visits values in sorted order. If two values were swapped, that sorted sequence will have one or two spots where a value drops instead of rising — and those drops point straight at the culprits.

We do an inorder walk keeping a prev pointer to the previously-visited node. Every time we find prev.val > n.val, we've hit a descent. On the first descent we record first = prev; on every descent we update second = n.

Why two cases? If the swapped nodes are adjacent in the inorder order, there's exactly one descent, and first and second are the two ends of it. If they're far apart, there are two descents; first sticks to the larger value from the first drop, and second moves to the smaller value of the last drop.

Example: tree gives inorder 1, 3, 4, 2. The only descent is 4 → 2, so first = 4 and second = 2. Swapping their values fixes the order to 1, 2, 3, 4.

At the end we just swap first.val and second.val. We only store a handful of node pointers, so the fix uses no extra data structures.

Time: O(n) Space: O(h)