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