Lowest Common Ancestor of a BST (LeetCode 235)

The problem

You get the root of a binary search tree and two values p and q that are both in the tree. Return their lowest common ancestor (LCA): the deepest node that has both p and q in its subtree. A node counts as an ancestor of itself.

In a BST, everything in a node’s left subtree is smaller than it and everything in its right subtree is larger.

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

            6
          /   \
         2     8
        / \   / \
       0   4 7   9
          / \
         3   5

Output: 6

2 is in 6’s left subtree and 8 is in its right, so 6 is the deepest node above both.

How to think about it

Start with brute force. Find the root-to-node path for p and for q, then walk both paths together until they diverge; the last shared node is the LCA. That works on any binary tree, but it ignores the BST ordering and uses O(h) memory for the paths.

The key insight: the ordering tells you which way both targets are. At any node, compare p and q with node.val. If both are smaller, both live in the left subtree, so the LCA is down there too. If both are larger, go right. The first node where they split (one on each side, or one equals the node) is the LCA. Below it they’d be in different subtrees, so no deeper node can hold both.

So you never branch. You follow a single path down, like a binary search. That turns an O(n) tree search into O(h), and a simple loop means no recursion at all.

Which pattern is this? A BST walk. The tell is the word “BST” plus a question about where two values sit relative to each other. Whenever you see a BST, ask how the ordering can replace a full DFS.

Approach

1. Start at the root.
2. If p and q are both less than root.val, move to root.left.
3. If both are greater, move to root.right.
4. Otherwise they split here (or one of them is this node): return root.val.

Solution

def lca_bst(root, p, q):
    while root:
        if p < root.val and q < root.val: root = root.left      # both on the left
        elif p > root.val and q > root.val: root = root.right   # both on the right
        else: return root.val                                   # they split here: this is the LCA
# lca_bst(tree[6,2,8,0,4,7,9], 2, 8) -> 6

This version takes p and q as values and returns a value. On LeetCode they are nodes, so compare p.val and q.val and return the node.

Dry run

Two runs on the example tree:

Complexity

• Time: O(h). You move down one level per step, so at most the tree height. That’s O(log n) for a balanced BST and O(n) for a skewed one.
• Space: O(1). A single pointer; no recursion and no stored paths.

Edge cases and pitfalls

• One target is the ancestor of the other (p = 2, q = 4): at node 2, neither “both smaller” nor “both larger” holds, so 2 is returned. That’s correct, since a node is its own ancestor.
• p > q is fine. The conditions check both values, so their order doesn’t matter.
• Use strict < and >. If you write <=, a target equal to the node sends you past the answer.
• Don’t reuse this on a plain binary tree. Without the ordering, the comparisons mean nothing; use the general LCA instead.

Related problems

• Lowest Common Ancestor of a Binary Tree (LeetCode 236): the same question without the BST ordering.
• Validate Binary Search Tree (LeetCode 98): the ordering this solution relies on, checked.
• Kth Smallest Element in a BST (LeetCode 230): another problem the BST ordering makes easy.