You are given the root of a binary search tree where the values of exactly two nodes were swapped by mistake. Recover the tree by restoring those two nodes (without changing its structure) and return the root.
The tree is given in level-order (breadth-first), using null for missing children; return it in the same format.
Input: root = [1, 3, null, null, 2] Output: [3, 1, null, null, 2] 1 and 3 were swapped; restoring them yields a valid BST.
Input: root = [3, 1, 4, null, null, 2] Output: [2, 1, 4, null, null, 3] 2 and 3 were swapped; swapping them back recovers the BST.
- The number of nodes is in the range [2, 10^4] - -2^31 <= Node.val <= 2^31 - 1 - Exactly two nodes were swapped
The defining property of a BST is that its inorder traversal is strictly increasing. Swapping two nodes' values breaks that sorted order in a predictable way — so recovery is about spotting where the inorder sequence dips.
The brute approach makes the property literal: do an inorder traversal to collect the nodes, take their values, sort them, and write them back in inorder order. It's O(n) time and O(n) space and always produces the valid BST.
The optimal approach finds the swapped pair during a single inorder pass using O(1) extra state (beyond recursion). Track the previously visited node prev. Whenever prev.val > cur.val, you've found a descent. If the two swapped nodes are non-adjacent there are two descents — the first offender is the prev of the first descent, the second is the cur of the second descent. If they're adjacent there is a single descent, and both offenders are that one prev/cur pair. Recording first = prev only on the first descent and second = cur on every descent handles both cases; swap their values at the end.
“How many nodes were swapped?”
Exactly two.
“Can I change the tree's shape?”
No — only fix the two values in place.
Inorder of a BST is sorted, so I do an inorder pass and look for where a value is smaller than the previous one.
The first such dip gives the first wrong node, the last dip gives the second; I swap their values.
Worked example — inorder 1 3 2 4, swapped nodes are 3 and 2
prev=1, cur=3 -> ok prev=3, cur=2 -> dip! first=3, second=2 prev=2, cur=4 -> ok swap 3 and 2 -> 1 2 3 4
The only places the sorted order breaks are at the swapped values.
Non-adjacent swaps cause two descents; adjacent swaps cause one.
This single rule handles both cases; swap their values at the end.
| Sort inorder values | Inorder anomaly scan | |
|---|---|---|
| Idea | Collect, sort, write values back | Find the two dips in one pass, swap |
| Time | O(n log n) | O(n) |
| Space | O(n) | O(height) |
Both restore the BST; the scan finds and swaps just the two offenders. Full code is in the Approaches selector below.
Key takeaway
A BST's inorder is sorted, so a swap shows up as one or two descents. Record the earlier node of the first descent and the later node of the last descent, then swap their values. O(n) time, O(height) space.
inorder: if prev.val > cur.val:
first = first or prev
second = cur
swap(first.val, second.val)