235. Lowest Common Ancestor of a Binary Search Tree

Finding a lowest common ancestor in a general tree usually means a full DFS, but a binary search tree hands you a shortcut most people miss on the first read. The values themselves tell you which way to turn. It belongs to the binary tree patterns family, and it’s the cleanest example of “the invariant does the searching for you.”

The problem

Given a BST and two nodes p and q that both live in it, return their lowest common ancestor — the deepest node that has both of them somewhere below it (a node counts as its own ancestor). (Full statement on LeetCode.)

Say the tree is rooted at 6 with 2 on the left and 8 on the right. The LCA of 2 and 8 is 6 — they sit on opposite sides of it. The LCA of 2 and its own child 4 is 2, because an ancestor can be the node itself.

Intuition: the split point is the answer

In a BST every value is greater than everything in its left subtree and smaller than everything in its right subtree. Walk down from the root and compare the current node’s value against both targets:

• If p and q are both smaller, they both live in the left subtree — go left.
• If they’re both larger, they’re both on the right — go right.
• Otherwise they straddle the current node (or one equals it), and this is the first place their paths diverge.

That straddle point is exactly the lowest common ancestor. There’s nothing deeper that still has both below it, because one step further would drop one of the targets out of the subtree. You never need to look at a subtree that can’t contain both, so the walk costs one step per level: $O(h)$, where $h$ is the tree height. On a balanced BST that’s $O(\log n)$.

Solution

Because each step only depends on the current node, you can loop instead of recurse and keep space at $O(1)$:

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode node = root;
        while (node != null) {
            if (p.val < node.val && q.val < node.val) {
                node = node.left;        // both targets are smaller — descend left
            } else if (p.val > node.val && q.val > node.val) {
                node = node.right;       // both are larger — descend right
            } else {
                return node;             // they split here (or one is this node): LCA
            }
        }
        return null;                     // unreachable: p and q are guaranteed present
    }
}

The else branch quietly covers the “a node is its own ancestor” case: when node is p, one comparison is false, so you stop and return it instead of walking past.

Complexity

	Time	Space
BST walk-down	$O(h)$	$O(1)$

$h$ is the height — $O(\log n)$ when the tree is balanced, $O(n)$ if it’s degenerate (a straight line). A recursive version reads just as cleanly but adds $O(h)$ stack frames.

In an interview

Say the key sentence up front: “this is a BST, so I don’t need a general LCA search — I can walk down until the two values split.” That single observation is what separates this from LCA of a general binary tree, which forces an $O(n)$ post-order DFS. The trap is reaching for that heavier traversal out of habit and never using the sorted-order property you were handed.

One edge worth naming: because a node can be its own ancestor, you must compare with < and >, not <=. If you go left the instant p.val <= node.val, you’d step past the target when p equals the current node. This same value-driven navigation powers Validate Binary Search Tree and Kth Smallest Element in a BST; the binary tree patterns hub collects the rest.

References

• LeetCode 235 — Lowest Common Ancestor of a Binary Search Tree