The O(n) Club: Lowest Common Ancestor in a Binary Tree: Recursion So Easy, Even Your Ancestors Could Do It

The O(n) Club: Lowest Common Ancestor in a Binary Tree: Recursion So Easy, Even Your Ancestors Could Do It

⚡ TL;DR

Want the lowest common ancestor of two nodes in a binary tree (emphasis on “binary tree”—forget BST shortcuts)? Run a recursive DFS. Return current node if it’s null, p, or q; otherwise, scan left and right. If both return something, boom—LCA! Java magic below:

// Definition for a binary tree node.
class TreeNode {
  int val;
  TreeNode left, right;
  TreeNode(int x) { val = x; }
}
 TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  if (root == null || root == p || root == q) return root;
  TreeNode left = lowestCommonAncestor(root.left, p, q);
  TreeNode right = lowestCommonAncestor(root.right, p, q);
  if (left != null && right != null) return root;
  return left != null ? left : right;
}

🧠 How Devs Usually Mess This Up

Here’s what happens when too much Stack Overflow, too little sleep, and a binary tree get together:

• BST Confusion: Using node values to pick sides, like you’re doing a BST problem. News flash: no ordering here. Branch at random and hope for the best? Not recommended.
• Parental Controls: Building full ancestor paths for both nodes like a caffeine-fueled genealogist, then walking the paths backward for an awkward family reunion. Sure, you’ll find a common granny, but wow, talk about overkill.
• Ignoring the Self-Ancestor Rule: If p is sitting on top of q (in literal code branches), p is the LCA. Don’t climb the tree for answers you’ve already tripped on.

🔍 What’s Actually Going On

Imagine a robot chef looking for the closest mutual supervisor of two sous-chefs on a kitchen org chart. The chef starts at the head honcho (root), pokes through every team (left/right subtree), and if both sous-chefs turn up from separate kitchens, he’s the big boss. If either is their own supervisor, that’s your answer—no further kitchen drama needed. It’s post-order DFS: search the food chain left, search right, then do something useful on the way back up.

🛠️ PseudoCode

• Return null if the node is null.
  

  if (node == null) return null;

  Empty trees have no ancestors. Sad, but true.

• Return node if you hit p or q.
  

  if (node == p || node == q) return node;

  Cakewalk: You’re sitting on your answer, don’t overthink it.

• Search left and right children recursively.
  

  TreeNode left = lowestCommonAncestor(node.left, p, q);
  TreeNode right = lowestCommonAncestor(node.right, p, q);

  Think: Cooking in both pans at once. What comes back?

• If both sides return non-null, you’re at the LCA.
  

  if (left != null && right != null) return node;

  If you’re getting results from both directions, congrats, you’re The Boss.

• Otherwise, return whichever side isn’t null.
  

  return left != null ? left : right;

  Keep bubbling up results like a hungry mutex.

💻 The Code

// Classic Java recursion—so short, your interviewer will grin.
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}
 public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) {
            return root;
        }
        return left != null ? left : right;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• BST? No Thanks: Don’t use node values for navigation. This is a plain old binary tree, not a sorted family photo.
• Ancestor Overlap: If one node is an ancestor of the other, it’s the LCA. No need for existential recursion.
• Janky Trees: Trees with cycles, multi-roots, or loose nodes? You have worse problems—this solution won’t save you.
• Time and Space? Both are O(h), h being the tree height (a.k.a. “stickiness”). That’s it. If your interviewer scowls about O(n), remind them some trees are just sad.

🧠 Interviewer Brain-Tattoo

“Most great recursion looks like cheating—return early, double-back, hand the dirty job to the call stack.”