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:

🧠 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

Otherwise, return whichever side isn’t null.

return left != null ? left : right;

Keep bubbling up results like a hungry mutex.

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.

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?

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.

Return null if the node is null.

if (node == null) return null;

Empty trees have no ancestors. Sad, but true.

💻 The Code

// Classic Java recursion&mdash;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 &amp;&amp; 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.