Recover Binary Search Tree
01 · Problem
You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. Restore the BST by swapping those two values back, without changing the tree's shape, and return the root.
All values are distinct, so the corrected tree is unique. Trees are given and returned in level-order form, with null marking missing children (trailing nulls omitted).
02 · Examples
root = [1,3,null,null,2]
[3,1,null,null,2]
3 cannot be the left child of 1 in a BST. Swapping the values 1 and 3 restores the ordering.
root = [3,1,4,null,null,2]
[2,1,4,null,null,3]
2 cannot sit in the right subtree of 3. Swapping 2 and 3 fixes the tree.
root = [2,3,1]
[2,1,3]
The two leaves were swapped; exchanging them gives a valid BST.
03 · Constraints
- 01The number of nodes in the tree is in the range [2, 1000].
- 02-231 <= Node.val <= 231 - 1
- 03All node values are unique.
- 04Exactly two node values have been swapped.
04 · Optimal complexity
- Time
- O(n)
- Space
- O(h)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.