Lowest Common Ancestor of a Binary Search Tree

MediumTreesTreeBinary Search TreeDFS

Problem

You are given the root of a binary search tree and two nodes guaranteed to exist in it. Find their lowest common ancestor: the deepest node in the tree that has both given nodes as descendants, where a node counts as its own descendant.

Example. In a binary search tree rooted at 6 with left subtree rooted at 2 (children 0 and 4) and right subtree rooted at 8, the lowest common ancestor of 2 and 4 is 2 itself, while that of 2 and 8 is the root 6.

Key idea

In a general binary tree, finding the lowest common ancestor requires searching both subtrees at every node and combining the results, since there is no way to know which side either target sits on without checking. A binary search tree gives that information for free: at any node, every left-subtree value is smaller and every right-subtree value is larger.

That ordering tells you exactly which way to go. Compare the current node's value to both targets. If both are smaller, move left; if both are larger, move right. The moment the targets fall on opposite sides of the current node, or one of them equals it, that node is the split point where the search paths diverge, and it is the answer. No backtracking or subtree combination is needed, so a single walk down from the root gets there directly.

Solution

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

function lowestCommonAncestor(root: TreeNode | null, p: TreeNode | null, q: TreeNode | null): TreeNode | null {
  let node = root;

  while (node !== null && p !== null && q !== null) {
    if (p.val < node.val && q.val < node.val) {
      // both targets are smaller, so the split point is further left
      node = node.left;
    } else if (p.val > node.val && q.val > node.val) {
      // both targets are larger, so the split point is further right
      node = node.right;
    } else {
      // targets are on opposite sides, or one equals this node: found the split point
      return node;
    }
  }

  return null;
}

Complexity

  • Time: O(h). The walk follows one path from the root, at most the tree's height, and O(log n) on a balanced tree.
  • Space: O(1) with an iterative walk, or O(h) if written recursively, for the call stack.

Watch out for

  • This ordering shortcut only holds because the tree is a binary search tree; the same comparisons are meaningless on a general binary tree.
  • Handle the case where one target is an ancestor of the other: stop as soon as the current node equals either target.
  • A skewed binary search tree degrades the walk to O(n), the same as a linked list.

Pattern

This is search-tree navigation: exploit an ordering invariant to discard one branch at every step instead of exploring both, the instinct behind binary search itself. Recognizing when a tree carries an ordering property, rather than treating it as an arbitrary shape, turns an O(n) tree problem into an O(h) one.

Related questions