Skip to main content

98. Recover Binary Search Tree

mediumAsked at Plaid

Two nodes in a BST have been swapped by mistake; recover the tree without changing structure. Plaid asks this because detecting and repairing two-row swap corruption in a sorted category tree (without rebuilding) is exactly this primitive.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Plaid loops.

  • Glassdoor (2025)— Plaid backend onsite — corruption-repair variant.
  • LeetCode Discuss (2026)— Plaid BST hard.

Problem

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

Constraints

  • The number of nodes in the tree is in the range [2, 1000].
  • -2^31 <= Node.val <= 2^31 - 1

Examples

Example 1

Input
root = [1,3,null,null,2]
Output
[3,1,null,null,2]

Example 2

Input
root = [3,1,4,null,null,2]
Output
[2,1,4,null,null,3]

Approaches

1. Inorder to array, swap values

Collect inorder; find the two out-of-order values; write back via a second inorder pass.

Time
O(n)
Space
O(n)
// Works. O(n) extra space.

Tradeoff: Allocates an array.

2. Inorder traversal with prev tracker

Inorder; track prev. When prev.val > curr.val, mark these as candidates. First mismatch: first = prev, second = curr. Second mismatch: second = curr (replacement).

Time
O(n)
Space
O(h) recursion
function recoverTree(root) {
  let first = null, second = null, prev = null;
  function inorder(n) {
    if (!n) return;
    inorder(n.left);
    if (prev && prev.val > n.val) {
      if (!first) first = prev;
      second = n;
    }
    prev = n;
    inorder(n.right);
  }
  inorder(root);
  [first.val, second.val] = [second.val, first.val];
}

Tradeoff: O(h) extra space. The 'first mismatch' logic finds the two swapped nodes — if they're adjacent in inorder, one mismatch; if not, two mismatches.

Plaid-specific tips

Plaid grades this on the two-mismatch handling — most candidates miss that the swapped nodes might be non-adjacent in inorder. Bonus signal: trace the recovery with a non-adjacent swap. Connect to category-tree corruption repair where two leaves get mis-assigned.

Common mistakes

  • Setting first = curr instead of prev on the first mismatch — gets the swap pair wrong.
  • Stopping after one mismatch — misses non-adjacent swaps.
  • Mutating tree structure instead of just values.

Follow-up questions

An interviewer at Plaid may pivot to one of these next:

  • Morris traversal for O(1) extra space.
  • Recover with k swaps allowed.
  • Detect arbitrary corruption (more than two swaps).

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why two mismatches sometimes?

If swapped nodes are adjacent in inorder, you see one descent. If they're separated by valid nodes, you see two separate descents.

Morris traversal?

O(1) space by temporarily threading the tree. Same algorithm otherwise. Useful for very large trees in production.

Practice these live with InterviewChamp.AI

Drill Recover Binary Search Tree and other Plaid interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →