188. Lowest Common Ancestor of a Binary Tree

Let recursion do the search. Each call returns: None if neither p nor q is in this subtree; the node itself if this node is p or q; otherwise whichever non-null result bubbled up. The first time both sides return non-null, the current node is sitting between them — that's the LCA.

What each recursive call returns

dfs(node) returns:

• None — neither p nor q lies in node's subtree.
• p or q — that target is found at or below node.
• The LCA itself — once two targets have been seen on opposite sides of node, the answer locks in and propagates up.

Steps

1. Base cases:
   • If root is None, return None.
   • If root is p or root is q, return root — we've found one of the targets, or the LCA could be this very node (when the other target is somewhere below).
2. Recurse into root.left → left.
3. Recurse into root.right → right.
4. Combine:
   • If both left and right are non-None, then p is on one side and q is on the other → root is the LCA. Return root.
   • Otherwise return left or right (whichever side, if either, found a target).

Walk-through

Tree:

        3
       / \
      5   1
     /|   |\
    6 2   0 8
      /|
     7 4

LCA of 5 and 1 should be 3. LCA of 5 and 4 should be 5. LCA of 7 and 8 should be 3.

Trace dfs(3) for finding LCA(5, 1):

dfs(3)
  dfs(5)  ← root is p, return node 5
  dfs(1)  ← root is q, return node 1
  left = 5, right = 1   → both non-null → return 3

Trace dfs(3) for LCA(5, 4):

dfs(3)
  dfs(5)  ← return node 5 (root matches)
  dfs(1)
    dfs(0) → None
    dfs(8) → None
    return None
  left = 5, right = None → return left = 5

The recursion at 5 short-circuits before exploring 4, but the answer is still correct because the LCA spec says one node can be a descendant of the other. When we hit 5 (which is p), we return it without checking that 4 actually lives below it — but 4 does live below 5, so the answer holds.

Why short-circuiting at p or q is safe

If we return p immediately on hitting it, we might not search p's subtree for q. But:

• If q is in p's subtree, then p itself is the LCA (one is the ancestor of the other). Returning p is correct.
• If q is not in p's subtree, then q will be found on a different branch via the other recursive call. The combine step will find both p and q as siblings and return the higher ancestor.

Edge cases

• p == q: any ancestor works; the algorithm returns p itself.
• p is the root: the very first call returns root immediately. Correct.
• Tree is a chain: O(n) recursion depth — fine for typical inputs.

Complexity

• Time: O(n) — every node visited at most once.
• Space: O(h) recursion stack.

class Solution {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

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