Lowest Common Ancestor of a Binary Search Tree

The problem. Given a binary search tree and two of its nodes p and q, return their lowest common ancestor — the deepest node that has both p and q in its subtree. A node counts as its own ancestor.

Example

root = [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]
p = 2, q = 8  ->  6
p = 2, q = 4  ->  2    (a node is its own ancestor)
p = 3, q = 5  ->  4
p = 7, q = 9  ->  8

The idea

In a general binary tree you'd have to search both subtrees. In a BST the values tell you where p and q are. If both are smaller than the current node, both live in the left subtree — so does their LCA. If both are bigger, go right. The first node where they split (one on each side, or one of them is the node) is the answer.

1. Ignore the order: general binary-tree LCA

The classic binary-tree solution works on a BST too: ask each subtree whether it contains p or q, and the node where both sides answer "yes" is the LCA.

1function lowestCommonAncestor(root, p, q) {2  if (root === null || 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 !== null && right !== null) return root;   // one on each side6  return left !== null ? left : right;7}

Time O(n), space O(h). It may visit every node — it never uses the ordering.

2. Recursion that follows the values

1function lowestCommonAncestor(root, p, q) {2  if (p.val < root.val && q.val < root.val) return lowestCommonAncestor(root.left, p, q);3  if (p.val > root.val && q.val > root.val) return lowestCommonAncestor(root.right, p, q);4  return root;                                         // they split here (or one of them is root)5}

Time O(h), space O(h) for the call stack — one call per level on a single path.

3. The same walk as a loop

1function lowestCommonAncestor(root, p, q) {2  let node = root;3  while (node !== null) {4    if (p.val < node.val && q.val < node.val) node = node.left;        // both on the left5    else if (p.val > node.val && q.val > node.val) node = node.right;  // both on the right6    else return node;                                                   // they split here7  }8  return null;9}

Time O(h), space O(1).

Comparing the approaches

Edge cases to test

Variations