DSA Tracker

Visualize

Recover Binary Search Tree

Inorder traversal tracking drops

time O(n)space O(h) recursion stack

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 ever appears, it means the swapped nodes were NOT adjacent in sorted order, so the second node is 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 = [3, 1, 4, null, null, 2] — exactly two nodes were swapped by mistake. Recover the BST without changing its structure. Expected output: [2, 1, 4, null, null, 3].

Problem:Recover Binary Search TreeMedium

Pattern:Binary Search Tree Problems

Inorder traversal tracking drops

step 1 / 10

1
3
2
4

Two nodes were swapped by mistake. An inorder walk that tracks a `prev` pointer will dip exactly where the swap broke the ascending order.

Pseudocode
1FUNCTION inorder(node):
2  IF node = null: RETURN
3  inorder(node.left)
4  IF prev != null AND prev.val > node.val:
5    IF first = null: first <- prev
6    second <- node
7  prev <- node
8  inorder(node.right)
9inorder(root)
10SWAP first.val AND second.val

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. Two nodes were swapped by mistake. An inorder walk that tracks a `prev` pointer will dip exactly where the swap broke the ascending order.
  2. Enter inorder(3). Recurse into its left subtree first.
  3. 1 has no left subtree and prev is still empty, so there is nothing to compare yet. Set prev = 1.
  4. prev(1) < 3, so no violation here. Set prev = 3.
  5. 3 has no more to do on its left or itself — recurse into its right subtree.
  6. Enter inorder(4). Recurse into its left subtree first.
  7. prev(3) > 2 — the BST order breaks here. Mark 3 as the first swapped node and 2 as the second (tentatively).
  8. prev(2) < 4, so no violation here. Set prev = 4.
  9. Traversal finished. Exactly one drop was found (3 then 2), which means the two swapped nodes are adjacent in sorted order.
  10. Swap the VALUES of 3 and 2 (never the pointers). 3 becomes 2 and 2 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.

Solve Recover Binary Search Tree in the editorAll BST problemsBack to roadmap