LeetCode 235 · Medium · Trees

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 of them in its subtree (a node counts as its own descendant).

O(h)time
O(1)space · no recursion
BST walkstop where p and q split

a valid BST in level order, distinct values · 2 to 15 nodes, 4 levels · values −99 to 99 · p ≠ q, both in the tree

cur's path root first · ringed = p and q · faded = subtrees ruled out

Sorted order the BST's in-order values · faded = ruled out · cur splits p and q when it lies between them

cur
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { TreeNode cur = root; while (cur != null) { if (p.val > cur.val && q.val > cur.val) { cur = cur.right; } else if (p.val < cur.val && q.val < cur.val) { cur = cur.left; } else { return cur; } } return null;}
p, q
—
cur
—
compare
—
steps down
0

Why it works

  1. Brute force ignores the ordering: record the root-to-p and root-to-q paths with a full search, then take the last node they share. O(n) time and O(n) space.
  2. The BST order tells you where p and q live. If both are bigger than cur, both sit in its right subtree, so every common ancestor below cur is on the right; same for the left. The first node where they fall on different sides (or that equals one of them) is the split point, and no deeper node can contain both.
  3. One step per level: the walk only goes down, so it costs O(h), which is O(log n) for a balanced tree and O(n) for a chain. Nothing is stored but cur: O(1) space.
  4. Pitfall: forgetting that a node is its own ancestor. When cur equals p (or q), the other one is below it, so cur is the answer; the else branch covers that because neither strict comparison holds.
  5. Related: for a plain binary tree (problem 236) there is no ordering, so you need a post-order search that reports which of p and q each subtree contains.