Visualize

Pattern visualizer

Recover Binary Search Tree

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. 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]..

Inorder traversal tracking drops

time O(n)space O(h) recursion stackstep 1 / 10
1
3
2
4
line 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.

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

Where to practice BST

Practice BST problemsAll BST problemsBack to roadmap