Lowest Common Ancestor of BST: LeetCode 235 Solution

LeetCode 235, Lowest Common Ancestor of a Binary Search Tree, is one of those problems that feels like it should be hard — until you realize the BST property hands you the answer. Unlike the general binary tree version (#236), you never need to search the entire tree.

The lowest common ancestor BST LeetCode problem asks you to find the deepest node that is an ancestor of both p and q. In a regular binary tree, that requires checking every node. In a BST, the ordering property gives you a direct navigation path.

This problem is a favorite in coding interviews because it tests whether you truly understand what makes a BST special. Let us walk through why the BST property makes this elegantly simple.

Given a binary search tree and two nodes p and q, find the lowest (deepest) node that has both p and q as descendants. A node is allowed to be a descendant of itself, so if p is an ancestor of q, then p is the LCA.

The key constraint is that this is a BST — every node in the left subtree is smaller than the root, and every node in the right subtree is larger. This ordering is what makes the LCA binary search tree problem fundamentally different from LCA in a general tree.

Consider a BST with root 6. If you are looking for the LCA of nodes 2 and 8, you know immediately that 2 is in the left subtree and 8 is in the right subtree. The only node where their paths diverge is 6 itself — that is your answer.

The lowest common ancestor explained in BST terms comes down to one observation: at each node, you can determine exactly where both p and q live. If both values are smaller than the current node, they are both in the left subtree. If both are larger, they are both in the right subtree. Otherwise, the current node is the LCA.

This three-way decision is the entire algorithm. You start at the root and follow the BST property downward. The moment p and q "split" — one goes left, one goes right — you have found the lowest common ancestor. This gives you BST LCA O(h) time complexity, where h is the height of the tree.

Why does this work? Because in a BST, the split point is the deepest node where both p and q can still be reached by going in the same direction. Once they diverge, no deeper node can be an ancestor of both.

The recursive approach for ancestor BST recursive follows the three conditions directly. If both p and q are less than root.val, recurse left. If both are greater, recurse right. Otherwise, return root. The base case is naturally handled — when the paths split, you return.

The iterative version is even cleaner. Use a while loop starting at the root. If both values are less than the current node, move left. If both are greater, move right. Otherwise, return the current node. No stack, no recursion — just a simple pointer traversal.

Both approaches run in O(h) time where h is the tree height. The iterative version uses O(1) space, while the recursive version uses O(h) for the call stack. For a balanced BST, h = log(n), making this extremely efficient.

Consider the BST [6,2,8,0,4,7,9,null,null,3,5]. For p=2 and q=8, start at root 6. Since 2 < 6 and 8 > 6, they split at the root — LCA is 6. One comparison, one answer.

Now try p=2 and q=4 on the same tree. At root 6, both 2 and 4 are less than 6, so move left to node 2. At node 2, p equals the current node, so the paths split here — LCA is 2. Notice that a node can be its own ancestor.

For p=3 and q=5, start at 6 (both less, go left), then at 2 (both greater, go right), then at 4 (3 < 4 and 5 > 4, split) — LCA is 4. You only visited 3 nodes out of 9 in the tree, demonstrating the O(h) efficiency.

When one node is the ancestor of the other, the ancestor itself is the LCA. This is handled naturally — when you reach that node, the other value will be in one of its subtrees, causing a split. The problem statement confirms a node can be a descendant of itself.

If p equals q, the answer is simply that node. The algorithm handles this because at the node itself, the split condition triggers (neither both-left nor both-right is true).

When the root is the answer, you return immediately on the first iteration. This happens whenever p and q are in different subtrees of the root, which is common in balanced BSTs.

LeetCode 235 is a masterclass in using the BST property to simplify search. The general LCA of Binary Tree (#236) requires visiting every node with post-order traversal — O(n) time. The BST version cuts that down to O(h) by leveraging the ordering invariant.

This pattern of exploiting BST ordering appears across many problems: Validate BST (#98), Kth Smallest Element (#230), and Search in BST (#700) all rely on the same insight. Recognizing when a problem gives you a BST instead of a generic tree is a critical interview skill.

Practice this problem with YeetCode flashcards to build instant pattern recognition. When you see "BST" in a problem, your first thought should be: how does the ordering property simplify this? That instinct will serve you well across dozens of tree problems.