5.5 Lowest Common Ancestor (LCA)

Demo: Lowest Common Ancestor of a Binary Tree — LC 236 (Medium — Amazon/Meta/Microsoft High)

Statement (Demo): Given the root of a binary tree and two nodes p and q, return their lowest common ancestor — the lowest node whose subtree contains both. Example: root=[3,5,1,6,2,0,8], p=5, q=1 → node 3 | ⚡ n ≤ 10⁵, all values unique

Approach: Ask every node: is p or q in my subtree? If both sides return non-null, this node is the LCA; if only one side does, pass that result up.

function lowestCommonAncestor(root, p, q) {
  if (!root || root === p || root === q) return root;
  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);
  if (left && right) return root; // one on each side → this is the LCA
  return left || right;
}

Complexity: Time O(n), Space O(h)