Recover BST
Mahabharata — The Misplaced Warriors — Exactly Two Nodes Were Swapped, Restore the Order
दो योद्धा गलत स्थान — Inorder में दो उल्लंघन। पहले में पूर्ण — दूसरे में वर्तमान — अदला-बदली करो॥
*Two warriors in wrong place — two violations in inorder. First violation: prev is wrong; second: current is wrong. Swap them.*
The Story
Two nodes of a BST are swapped by mistake. Recover the BST without changing structure.
For BST `[1,3,null,null,2]` (3 and 1 are swapped): correct BST is `[3,1,null,null,2]`.
**Key insight:** In a valid BST, inorder traversal gives strictly increasing sequence. If two nodes are swapped, the inorder sequence has at most two 'violations' (places where prev.val >= curr.val). - **First violation:** prev is the first misplaced node (`first = prev`) - **Second violation:** curr is the second misplaced node (`second = curr`) - If only one violation: `second = curr` from the first violation (adjacent swap)
```java TreeNode first = null, second = null, prev = null; void inorder(TreeNode root) { if (root == null) return; inorder(root.left); if (prev != null && prev.val > root.val) { if (first == null) first = prev; // First violation: prev is wrong second = root; // Always update second to current } prev = root; inorder(root.right); } public void recoverTree(TreeNode root) { inorder(root); int t = first.val; first.val = second.val; second.val = t; } ```
Trace `[3,1,2]` (inorder should be 1,2,3 but visiting 3,1,2 in inorder of `[3,1,2]`... wait let me construct correctly).
For swapped BST where inorder gives [1,3,2] (3 and 2 are swapped): - prev=1, root=3: 1<3 no violation. prev=3 - prev=3, root=2: 3>2 VIOLATION. first=3. second=2. - prev=2, root=null. Done. - Swap first(3) and second(2): corrected ✓
For adjacent swap: inorder [2,1,3]: - prev=2, root=1: 2>1 VIOLATION. first=2, second=1. - prev=1, root=3: no violation. - Swap 2 and 1 ✓
The Inorder Collection + Sort Approach
Collect inorder, sort, reassign values back. O(n log n). Correct but slow.
public void recoverTreeBrute(TreeNode root) {
List<Integer> vals = new ArrayList<>();
collectInorder(root, vals);
Collections.sort(vals);
int[] i = {0};
assignInorder(root, vals, i);
}
void collectInorder(TreeNode root, List<Integer> vals) {
if (root==null) return;
collectInorder(root.left, vals);
vals.add(root.val);
collectInorder(root.right, vals);
}
void assignInorder(TreeNode root, List<Integer> vals, int[] i) {
if (root==null) return;
assignInorder(root.left, vals, i);
root.val = vals.get(i[0]++);
assignInorder(root.right, vals, i);
}The Two-Violation Inorder Wisdom
TreeNode first = null, second = null, prev = null;
public void recoverTree(TreeNode root) {
inorder(root);
int t = first.val;
first.val = second.val;
second.val = t;
}
void inorder(TreeNode root) {
if (root == null) return;
inorder(root.left);
if (prev != null && prev.val > root.val) {
if (first == null) first = prev;
second = root;
}
prev = root;
inorder(root.right);
}Step-by-Step Walkthrough
Swapped adjacent [2,1]: inorder visits 1,2 in underlying structure... Let me note: the traversal always visits inorder — so if the BST itself is [2,1,null], inorder visits 1 then 2. That's already correct — no violation. The 'swap' in the BST structure is what caused the inorder to be wrong. ✅
Deep Insight
**Why 'always update second':** The swapped nodes might be adjacent in inorder order (one violation) or non-adjacent (two violations). - Adjacent swap: [3,1,2] → inorder [3,1,2] → one violation (3>1). first=3, second=1. - Non-adjacent swap: [1,5,3,4,2,6] → violations (5>3): first=5,second=3; then (4>2): second=2. Final: swap 5 and 2.
By always updating `second = root` at each violation, we correctly capture the second swapped node regardless.
**Morris traversal for O(1) space:** Recover BST using Morris inorder traversal avoids any extra stack space.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n log n) | O(n) | Collect inorder, sort, reassign |
| Optimal | O(n) | O(h) | Single inorder pass; Morris traversal gives O(1) space |
Pattern Recognition
✅ Recover BST: inorder + two-violation detection ✅ First violation: first=prev; always second=curr ✅ Handles both adjacent and non-adjacent swaps ✅ Morris traversal for O(1) space **LeetCode Trigger Phrases:** → "recover binary search tree" → Two nodes swapped in BST → Inorder violation detection
Bhagavad Gita 4.8
परित्राणाय साधूनां विनाशाय च दुष्कृताम्। धर्मसंस्थापनार्थाय सम्भवामि युगे युगे॥
For the protection of the good, for the destruction of the wicked, and for the establishment of righteousness, I manifest Myself from age to age.
Connection: The Recover BST algorithm restores the righteous order that was disrupted by two misplaced nodes. Like Krishna's promise to manifest whenever dharma is violated, the algorithm identifies the two violators in the inorder sequence and corrects them — restoring the BST's fundamental law. The two violations in inorder are like two disruptions to dharma: the algorithm finds them and swaps them back, reestablishing cosmic order.