235. Lowest Common Ancestor of a Binary Search Tree

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

Record the search path from the root to p and to q. The LCA is the last node the two paths share. This works for any tree if you swap the BST search for a DFS.

1function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode {
2  const path = (target: TreeNode) => {
3    const out: TreeNode[] = [];
4    for (let n: TreeNode | null = root; n; n = target.val < n.val ? n.left : n.right) {
5      out.push(n);
6      if (n === target) break;
7    }
8    return out;
9  };
10  const a = path(p), b = path(q);
11  let i = 0;
12  while (i < a.length && i < b.length && a[i] === b[i]) i++;
13  return a[i - 1];
14}

tree

path to p

path to q

Record the root-to-node path for p and for q.

1 / 0

Space: play/pause · ←/→: step