Faangprep Logo
Log inStart free
Browse curriculum

Recover Binary Search Tree

Repair a binary search tree in which exactly two nodes' values were swapped, without changing its structure, by finding where the inorder sequence stops increasing.

MediumSolve on LeetCode

Problem Understanding

Recover Binary Search Tree: the values of exactly two nodes of a binary search tree were swapped by mistake. Recover the tree without changing its structure.

Examples: [1,3,null,null,2] → [3,1,null,null,2]; [3,1,4,null,null,2] → [2,1,4,null,null,3].

The Intuition: A Sorted List With Two Elements Swapped

Read the tree in inorder, as in Binary Tree Inorder Traversal, and it becomes a sorted list with two entries swapped:

  1. Find the drops where a value is smaller than the previous one.
  2. First wrong value: the larger side of the first drop.
  3. Second wrong value: the smaller side of the last drop (the same drop if there is only one).
  4. Swap them back.

The increasing-inorder check is the same one Validate Binary Search Tree relies on.

Interactive Walkthrough

#n = INORDER POSITION · RED = OUT OF PLACE

INORDER SHOULD INCREASE

first

:

second

:

inorder so far

None yet

 

Walk the tree in inorder. In a valid BST every value is larger than the one before it; look for drops

Next

1 is the first value in inorder

Free preview: the first 3 of 7 steps

root

Each visited node shows its inorder position. The previous node is outlined, suspects turn red when a drop exposes them, and they turn green once swapped. Try Far apart for the two-drop case.

Dry Run Table

Input: [3,1,4,null,null,2], inorder 1, 3, 2, 4.

prev node Drop? first second
- 1
1 3 no
3 2 yes 3 2
2 4 no 3 2

Swap 3 and 2. Answer: [2,1,4,null,null,3].

The Solution Template

One recursive inorder walk, then a swap.

Recover Binary Search Tree Code
1var recoverTree = function(root) {
2    let prev = null, first = null, second = null;
3    const inorder = (node) => {
4        if (!node) return;
5        inorder(node.left);
6        if (prev && prev.val > node.val) {
7            if (!first) first = prev;
8            second = node;
9        }
10        prev = node;
11        inorder(node.right);
12    };
13    inorder(root);
14    [first.val, second.val] = [second.val, first.val];
15};

Edge Cases & Common Mistakes

  • Adjacent swap: only one drop; set second on every drop so it is still found.
  • Setting first on every drop: overwrites it with the wrong node in the two-drop case.
  • Root involved: the method does not care where the nodes are.
  • Comparing with parents only: a swap can break the BST order far from the parent link.
  • Static state in C/Java: reset prev, first and second before each call.

Summary

Walk inorder tracking the previous node; at the first drop record the larger value's node, at every drop record the smaller value's node; swap the two values. O(n) time, O(h) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Vertical Order Traversal of a Binary Tree

Next

Construct Binary Search Tree from Preorder Traversal

The approach, step by step

  1. Walk inorder

    Traverse left subtree, node, right subtree, remembering the previous node.

  2. Spot drops

    When prev.val > node.val: set first = prev if it is unset, and set second = node every time.

  3. Swap

    After the walk, swap first.val and second.val.

Frequently asked questions

Why look at the inorder sequence?

Inorder visits a BST in increasing order, so the swap shows up as places where a value is smaller than the one just before it. Swapping two values of an increasing sequence creates one such drop if they were neighbors, and two drops otherwise.

Why the larger value of the first drop and the smaller of the last?

The value that moved earlier in the sequence is too big, so it shows up as the left side of the first drop. The value that moved later is too small, so it is the right side of the last drop. When there is only one drop, those are the two sides of that same drop, which is why the code sets second on every drop.

Can it be done in O(1) space?

Yes, with Morris inorder traversal, which threads each node's inorder predecessor back to it instead of using a stack, then removes the threads. The drop-detection logic stays the same; only the traversal changes.

Why swap values instead of relinking nodes?

The structure is fine; only two values are in the wrong places. Swapping the two values is O(1) and gives back the valid BST. Moving nodes would also require fixing parent and child links.

New to the technique behind this problem? Watch it run step by step:

Depth First Search Visualization

Applying for software engineering roles? Free, no sign-up:

AI resume checker: match your resume to the job description