Lowest Common Ancestor of a Binary Tree

Difficulty: Medium

Problem

Given a binary tree and two nodes p and q that exist in it, return their lowest common ancestor (LCA) — the DEEPEST node that has both p and q in its subtree. One convention matters a lot here: a node counts as an ancestor of ITSELF.

Example

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: Node 5 lives in 3's left subtree and node 1 in its right subtree. No deeper node contains both, so their lowest common ancestor is 3.

Brute-force approach

There is no separate brute-force phase — the split-point recursion IS the standard solution. (A heavier alternative — computing both root-paths and comparing — is discussed in the complexity phase.)

Optimal approach

Key insight: Ask every subtree: 'did you find p or q?' The deepest node whose LEFT and RIGHT both answer yes is where the searches meet — the LCA.

Ask every subtree whether it contains p or q. A found target (or decided LCA) travels upward; the deepest node that hears news from BOTH sides is the answer.

Steps

  1. Base case: null finds nothing — return null
  2. If this node IS p or q, return it immediately
  3. Ask the left subtree, then the right subtree
  4. Both returned something? This node is the split point — return it
  5. Otherwise relay whichever side found something (or null)

Time complexity: O(n) · Space complexity: O(h) where h = height of tree