Lowest Common Ancestor of a Binary Tree (LC 236)

Pattern: DFS - Post-Order Result Bubbling
Difficulty: Medium
Key Concept: Use recursion to “bubble up” found nodes; the split point is the LCA

Problem Statement

Given a binary tree, find the lowest (deepest) node that has both node p and node q as descendants. A node can be a descendant of itself.

• Input: TreeNode root, TreeNode p, TreeNode q
• Output: TreeNode (the LCA)

---

Clarifying Questions (Interview Style)

1. Do p and q always exist in the tree? → Yes
2. Can a node be a descendant of itself? → Yes (standard LCA definition)
3. Are node values unique? → Yes
4. BST or general Binary Tree? → General (more complex)

---

Brute Force: Store Paths - O(n) time, O(n) space

Find path from root to p and root to q, then compare.

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        List<TreeNode> pathP = new ArrayList<>();
        List<TreeNode> pathQ = new ArrayList<>();
        findPath(root, p, pathP);
        findPath(root, q, pathQ);

        TreeNode lca = root;
        for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
            if (pathP.get(i) == pathQ.get(i)) {
                lca = pathP.get(i);
            } else break;
        }
        return lca;
    }

    private boolean findPath(TreeNode root, TreeNode target, List<TreeNode> path) {
        if (root == null) return false;
        path.add(root);
        if (root == target) return true;
        if (findPath(root.left, target, path) || findPath(root.right, target, path)) return true;
        path.remove(path.size() - 1);
        return false;
    }
}

---

Optimal: Post-Order DFS - O(n) time, O(h) space

Logic at each node:

1. If I am p or q, return myself
2. Ask left subtree: “Do you have p or q?”
3. Ask right subtree: “Do you have p or q?”
4. If both returned non-null → I am the split point (LCA)
5. If only one returned non-null → pass it up
6. If both null → return null

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;
    }
}

---

Dry Run

Tree: p=5, q=1

      3
     / \
    5   1
   / \ / \
  6  2 0  8

1. LCA(3, 5, 1) calls LCA(5, 5, 1)
2. LCA(5, 5, 1) → base case (root == p) → returns 5
3. LCA(3, 5, 1) calls LCA(1, 5, 1)
4. LCA(1, 5, 1) → base case (root == q) → returns 1
5. Back at node 3: left=5, right=1 → both non-null → return 3

Case: p=5, q=2 (LCA is one of the nodes)

LCA(3)
 ├── LCA(5) → returns 5 (base case: root == p)
 │   (doesn't even recurse into children)
 └── LCA(1) → returns null (neither p nor q found)
Result: 5 (only left is non-null)

---

Edge Cases

• One node is the ancestor of the other: Handled by base case root == p || root == q
• Very large tree (10^7 nodes): Recursive may hit StackOverflowError → use iterative with parent pointer map
• p or q might not exist: Current code returns whichever exists. Add verification pass if needed.

---

Pattern Recognition

• Pattern: Tree Post-Order Result Bubbling
• Trigger: “Find a node connecting X and Y”, “distance between two nodes”, “property in subtrees”
• Similar Problems: Diameter of Binary Tree, Path Sum III, Distribute Coins in Binary Tree

---

Complexity

Approach	Time	Space	Notes
Store Paths	O(n)	O(n)	Two passes + path storage
Post-Order	O(n)	O(h)	Single pass, h = height