The problem. The values of exactly two nodes of a binary search tree were swapped by mistake. Put them back without changing the tree's structure (swap the values in place; return nothing).
root = [1, 3, null, null, 2] -> [3, 1, null, null, 2] (1 and 3 were swapped)
root = [3, 1, 4, null, null, 2] -> [2, 1, 4, null, null, 3] (2 and 3 were swapped)A BST's in-order walk is increasing. Swapping two values creates either one drop (if they were neighbours in sorted order, like 1 3 2 4) or two drops (like 1 5 3 4 2 6: drops at 5→3 and 4→2). In both cases, the first wrong value is the bigger side of the first drop, and the second wrong value is the smaller side of the last drop.
Collect the values in-order, sort them, and overwrite the nodes in in-order again. It fixes any number of misplaced values, not just two.
function recoverTree(root) { const nodes = []; const inorder = (node) => { if (node === null) return; inorder(node.left); nodes.push(node); inorder(node.right); }; inorder(root); const sorted = nodes.map((n) => n.val).sort((a, b) => a - b); nodes.forEach((n, i) => { n.val = sorted[i]; }); // in-order position i gets the i-th smallest}Time O(n log n), space O(n).
Compare each in-order node with the previous one; a drop marks a swapped node.
function recoverTree(root) { let prev = null, first = null, second = null; const inorder = (node) => { if (node === null) return; inorder(node.left); if (prev !== null && prev.val > node.val) { // a drop if (first === null) first = prev; // bigger side of the first drop second = node; // smaller side of the latest drop } prev = node; inorder(node.right); }; inorder(root); [first.val, second.val] = [second.val, first.val];}Time O(n), space O(h) for the recursion.
The follow-up asks for constant space. Morris traversal walks in-order without a stack: before going left, it makes the rightmost node of the left subtree point back to the current node (a temporary "thread"), and removes the thread the second time it arrives. The drop check is the same as approach 2.
function recoverTree(root) { let prev = null, first = null, second = null; const visit = (node) => { if (prev !== null && prev.val > node.val) { if (first === null) first = prev; second = node; } prev = node; }; let node = root; while (node !== null) { if (node.left === null) { visit(node); node = node.right; continue; } let pred = node.left; // rightmost node of the left subtree while (pred.right !== null && pred.right !== node) pred = pred.right; if (pred.right === null) { pred.right = node; // thread back, then go left node = node.left; } else { pred.right = null; // second arrival: remove the thread visit(node); node = node.right; } } [first.val, second.val] = [second.val, first.val];}Time O(n), space O(1). Each edge is walked at most a few times, and every thread is removed, so the tree ends up exactly as it started — apart from the fixed values.
