236. Lowest Common Ancestor of a Binary Tree

Given a binary tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q as descendants (a node counts as its own descendant).

Return p or q if found in a subtree, else null. If both subtrees return something, this node is the split point: the LCA. Otherwise pass up whichever side found something.

1function lowestCommonAncestor(root: TreeNode | null, p: TreeNode, q: TreeNode): TreeNode | null {
2  if (!root || root === p || root === q) return root;
3  const left = lowestCommonAncestor(root.left, p, q);
4  const right = lowestCommonAncestor(root.right, p, q);
5  if (left && right) return root;
6  return left ?? right;
7}

tree

At 3: search the left subtree.

1 / 0

Space: play/pause · ←/→: step