The O(n) Club: Recovering a Corrupted BST: When Two Nodes Pull a Freaky Friday
⚡ TL;DR
If two nodes in a BST have swapped their values, don’t panic—just do an in-order traversal, find the two sore thumbs where order is broken, and swap their values back.
Brute force? Yes, you could dump everything into a list, sort, and reassign. But that’s the inefficient, RAM-eating, stress-snacking way.// Brute force: please, no! List<Integer> vals = new ArrayList<>(); inorder(root, vals); Collections.sort(vals); fillTree(root, vals); // The classy way is coming up next.👇
🧠 How Devs Usually Mess This Up
Classic rookie move: people reach for the pointer-wrangling toolkit and try to swap the actual nodes (no—you don’t want to play Frankenstein here). Another mistake: assuming the swapped nodes are neighbors in in-order traversal. Sometimes they’re besties, sometimes they live on different continents. If you only test one case, the other one will haunt your production deploys.
🔍 What’s Actually Going On
Visualize your BST as a library shelf, sorted alphabetically. An exasperated intern swaps “Moby Dick” with “Zen and the Art of Motorcycle Maintenance”. When you scan the shelf in order, you’ll notice two abrupt breaks where the books shout, “I do NOT belong here!” Those two nodes? Swap their values. The branch structure stays untouched—just like you would never start rearranging the shelves themselves when a book is out of place.
If your swapped nodes were neighbors, you’ll spot a single jarring transition. If not, you’ll spot two. Either way, channel your inner librarian and put the offenders back where they belong.
🛠️ PseudoCode
- Do an in-order traversal (left, node, right). Trust in the process.
void traverse(TreeNode node) { if(node == null) return; traverse(node.left); // process traverse(node.right); } - Keep track of the last node you visited. Spot when the current node’s value is LESS than the previous. That’s a red flag.
- On the first red flag: Save both the previous and current nodes.
On a second red flag: Update the current node as the second swap buddy. - After traversal, swap the values of the two confused nodes. Shelf harmony restored.
💻 The Code
class Solution {
TreeNode first = null, second = null, prev = new TreeNode(Integer.MIN_VALUE);
public void recoverTree(TreeNode root) {
inorder(root);
// Just a value swap—cheaper than therapy.
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void inorder(TreeNode node) {
if (node == null) return;
inorder(node.left);
if (first == null && prev.val >= node.val)
first = prev;
if (first != null && prev.val >= node.val)
second = node;
prev = node;
inorder(node.right);
}
}
⚠️ Pitfalls, Traps & Runtime Smacks
- Swapping Nodes vs Values: You swap values, not actual nodes—don’t get click-happy with pointers.
- One Glitch or Two: Test both scenarios: swapped nodes as neighbors and swapped nodes separated by much drama.
- Space Complexity: Recursive calls mean you’re using O(H) space (tree height), not O(1). Morris Traversal exists for the show-offs and masochists.
- Degenerate BSTs: Don’t forget about trees that are basically a stick (full left or right). They need love too.
🧠 Interviewer Brain-Tattoo
“The only thing you should swap in a tree recovery problem is the bug and your own self-doubt… Oh, and two values.”
