Lowest Common Ancestor of a Binary Search Tree

Examples

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

2 lives in the left subtree of 6 and 8 lives in the right subtree, so 6 is the deepest node that has both underneath it.

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

4 is a descendant of 2, and a node is allowed to be its own ancestor, so 2 is the answer.

Constraints

• The number of nodes is in the range [2, 10^5].

• All node values are unique.

• p and q both exist in the tree and p != q.

Approach

A solution that works on any binary tree has to recursively search the left and right subtrees and see where p and q each turn up. That works here too, but it ignores something powerful: this tree is sorted.

Because it's a BST, you can tell which subtree a value lives in just by comparing it to the current node — no searching required. Walking down from the root, the first node where p and q stop agreeing on "which side" is exactly the split point, and therefore the lowest common ancestor.

Solutions

General Tree Approach — Recursive Search

This approach ignores the BST property entirely and treats the tree as an arbitrary binary tree, which makes it correct everywhere but not the fastest option available here.

At each node, recurse into the left and right subtrees looking for p and q. If a node itself is p or q, or if the search comes back "found something" from both children, then this node is the split point — return it upward. Otherwise pass along whichever side actually found something.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function lowestCommonAncestor(root, p, q) {
  if (root === null || root === p || root === q) return root;

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

  if (left !== null && right !== null) return root;
  return left !== null ? left : right;
}

Time: O(n) · Space: O(h) — recursion stack, where h is the tree's height

Optimal — Use BST Ordering

Instead of searching both subtrees, use the fact that a BST tells you exactly where a value belongs just from comparisons.

Start at the root. If both p.val and q.val are smaller than the current node's value, the split point must be somewhere in the left subtree, so move left. If both are larger, move right. The moment that's no longer true — one value is smaller and the other isn't, or one of them equals the current node — you're standing on the lowest common ancestor.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

function lowestCommonAncestor(root, p, q) {
  let node = root;

  while (node !== null) {
    if (p.val < node.val && q.val < node.val) {
      node = node.left;
    } else if (p.val > node.val && q.val > node.val) {
      node = node.right;
    } else {
      return node;
    }
  }

  return null;
}

Time: O(h) — one pass down the tree, where h is its height · Space: O(1) — iterative, no recursion stack