Recover Binary Search Tree (Swap Nodes)
Inorder traversal tracking drops, with a second-drop reassignment
A valid BST's inorder traversal is strictly ascending. Swapping two nodes' values creates one or two places where that order dips. Walk the tree inorder while remembering the last node visited (prev). The first time prev.val exceeds the current node's value, prev is the first misplaced node and the current node is a tentative second. If a second dip appears later, the swapped nodes were NOT adjacent in sorted order — the second node must be updated to whichever node caused that later dip. Once the traversal finishes, swapping the two identified nodes' VALUES (never their pointers) restores the BST.
Details
Animated on: root = [1, 3, null, null, 2] — exactly two nodes were swapped by mistake. Recover the BST without changing its structure. Expected output: [3, 1, null, null, 2].
Problem:Recover Binary Search Tree (Swap Nodes)Medium
Inorder traversal tracking drops, with a second-drop reassignment
step 1 / 8
Two nodes were swapped by mistake. An inorder walk that tracks a `prev` pointer will dip exactly where the swap broke the ascending order.
1FUNCTION inorder(node):2 IF node = null: RETURN3 inorder(node.left)4 IF prev != null AND prev.val > node.val:5 IF first = null: first <- prev6 second <- node7 prev <- node8 inorder(node.right)9inorder(root)10SWAP first.val AND second.val
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Two nodes were swapped by mistake. An inorder walk that tracks a `prev` pointer will dip exactly where the swap broke the ascending order.
- Enter inorder(1). Recurse into its left subtree first.
- 3 has no left subtree and prev is still empty, so there is nothing to compare yet. Set prev = 3.
- 3 has no more to do on its left or itself — recurse into its right subtree.
- prev(3) > 2 — the BST order breaks here. Mark 3 as the first swapped node and 2 as the second (tentatively).
- prev(2) > 1 — a SECOND drop. Since first(3) is already set, this means the earlier tentative second (2) was not the real swap partner — update second to 1 instead.
- Traversal finished. Two drops were found, which means the swapped nodes (3 and 1) are NOT adjacent in sorted order — that is why second had to be updated mid-walk.
- Swap the VALUES of 3 and 1 (never the pointers). 3 becomes 1 and 1 becomes 3 — the tree's shape is untouched.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.