#236 - Lowest Common Ancestor of a Binary Tree

MediumBinary Tree - DFS

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). The LCA is the deepest node that is an ancestor of both p and q (a node can be an ancestor of itself).

Input	Output
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1	3
root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4	5
root = [1,2], p = 1, q = 2	1

Solution Space

Try it

/**
 * Finds the lowest common ancestor of nodes p and q in a binary tree.
 *
 * @param root Root of the binary tree
 * @param p    First target node
 * @param q    Second target node
 * @returns    The LCA node
 */
export function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode,
  q: TreeNode,
): TreeNode | null {
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // If both sides returned non-null, this node is the LCA
  if (left && right) return root;

  // Otherwise, the non-null side contains both p and q
  return left ?? right;
}

Approach: recursive DFS – returns the current node if it's `p` or `q`; if both subtrees return non-null, the current node is the LCA; otherwise propagate the non-null result upward.

Time: O(n) – visits each node at most once.

Space: O(h) – recursion stack.

#104 Maximum Depth of Binary Tree

#437 Path Sum III