The O(n) Club: Lowest Common Ancestor in a BST — The Ancestor Hunt Nobody Asked For

The O(n) Club: Lowest Common Ancestor in a BST — The Ancestor Hunt Nobody Asked For

⚡ TL;DR

Want to find the nearest shared ancestor in a BST? Start at the root and march down: go left if both are smaller, right if both are bigger, and stop when paths split. Easy as pizza. Here’s the slick logic:

// Just walk the tree, no recursion needed
TreeNode current = root;
while (current != null) {
    if (p.val < current.val && q.val < current.val) current = current.left;
    else if (p.val > current.val && q.val > current.val) current = current.right;
    else return current; // Found the split or match
}

🧠 How Devs Usually Mess This Up

Picture a dev who grabs the generic binary tree hammer and tries to smash this nail: full traversals, temp parent pointers, or recursive detours as if every tree is a tangled mess. But hey, this is a BST, where order reigns and left/right means something. And no, the LCA doesn’t always lurk in the leaves—it can be one of the nodes itself. Also: duplicate values? That’s classic undefined territory. Stay unique, friends.

🔍 What’s Actually Going On

Here’s your analogy: the BST is a well-organized family reunion. You’re hunting for p and q. If both keep choosing the buffet line to the left, follow them; if they run to the right for dessert, chase them. The *moment* their paths diverge (or you literally bump into one of them), that’s the branch’s lowest common ancestor: the uncle they both regret sitting next to. No drama, no endless sibling searching.

🛠️ PseudoCode

• Start at the root.
  

  TreeNode current = root;

• Repeat while you’re not lost:
  
  • If p and q both < current, go left
  • If both > current, go right
  • If they split or you match one, boom: lowest common ancestor found

  while (current != null) {
      if (p.val < current.val && q.val < current.val) current = current.left;
      else if (p.val > current.val && q.val > current.val) current = current.right;
      else return current;
  }

• If you wander off the end, return null (something’s broken in tree-town).

💻 The Code

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode current = root;
        while (current != null) {
            if (p.val < current.val && q.val < current.val) {
                current = current.left;
            } else if (p.val > current.val && q.val > current.val) {
                current = current.right;
            } else {
                return current;
            }
        }
        return null;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Trying to use a generic binary tree approach? Congratulations, you’ll waste cycles and time. Use the order—follow the values!
• LCA could be one of your nodes (the ancestor isn’t always some distant relative!)
• Busting out duplicate values? Don’t. Classic BSTs are all about unique entries. You want chaos, try a database merge.
• Time complexity: O(h) — h is the height. For balanced BSTs, O(log n). If it’s a technically a stick, well… O(n).
• Space complexity: O(1) if you keep it iterative. (Your call stack will thank you by not blowing up.)

🧠 Interviewer Brain-Tattoo

“BST LCA: Because why search the whole family tree when you can just let order guide you straight to the drama?”