Lowest Common Ancestor of a BST: Leverage the Sorted Structure

You are given a binary search tree and two nodes, p and q. Find their lowest common ancestor (LCA), which is the deepest node that has both p and q as descendants. A node counts as a descendant of itself.

This is LeetCode 235: Lowest Common Ancestor of a Binary Search Tree. If you have already solved the general binary tree version (LeetCode 236), you might be tempted to reuse that same post-order DFS approach. It works, but it ignores the most powerful property you have been given: this tree is sorted.

Why the BST property changes everything

In a general binary tree, you have no idea where p and q might be. You have to search both subtrees for every node, which means O(n) time in the worst case.

A BST gives you a compass. At every node, you know exactly which direction each target lies:

• If a value is smaller than the current node, it must be in the left subtree.
• If a value is larger than the current node, it must be in the right subtree.

This means you never need to search both subtrees. At each step, you either go left, go right, or stop. That is the entire algorithm.

The key insight: finding the fork point

The LCA is the first node where p and q "split" into different subtrees. Think of it this way:

• If both p and q are smaller than the current node, they are both in the left subtree. The LCA must be further left.
• If both p and q are larger than the current node, they are both in the right subtree. The LCA must be further right.
• Otherwise, one is to the left and one is to the right (or the current node equals one of them). The current node is the fork point. That is your LCA.

You are just walking down the tree until the paths to p and q diverge. The node where they diverge is the answer.

The solution

def lowest_common_ancestor(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root

That is it. No recursion needed. No stack, no hash map, no parent pointers. Just a single while loop that walks down the tree.

Let's break down each branch:

• if p.val < root.val and q.val < root.val: Both targets are smaller. The LCA cannot be this node or anywhere in the right subtree. Move left.
• elif p.val > root.val and q.val > root.val: Both targets are larger. The LCA cannot be this node or anywhere in the left subtree. Move right.
• else: The values straddle the current node, or one of them equals the current node. Either way, this is the fork point. Return it.

The else clause covers three sub-cases all at once: p on the left and q on the right, p on the right and q on the left, or one of them being equal to the current node. All three mean the same thing: you have found the LCA.

Visual walkthrough

Let's trace through two examples on the BST [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]. Watch how the algorithm navigates down the tree until it finds the fork point.

Notice how fast this is. In the first example (p=2, q=8), we find the answer at the root in a single comparison. In the second example (p=2, q=4), we take just two steps. We never visit nodes that are irrelevant to our search. That is the power of the BST property.

Complexity analysis

Time is O(h) where h is the height of the tree. At each step, you move one level down. For a balanced BST, h = log n. For a skewed tree, h = n. This is strictly better than the general binary tree solution, which is always O(n).

Space is O(1). The iterative approach uses only a single pointer variable. No recursion, no auxiliary data structures.

Compare this to the general LCA solution on a regular binary tree: O(n) time and O(h) space. The BST property buys you a significant improvement on both fronts.

The building blocks

This problem uses one core pattern:

1. BST-guided search. The BST invariant (left children are smaller, right children are larger) lets you make a binary decision at each node. You never explore both subtrees. This same navigation pattern appears in search, insertion, deletion, and validation of BSTs. The skeleton looks like this:

while node:
    if target < node.val:
        node = node.left
    elif target > node.val:
        node = node.right
    else:
        return node

For the LCA problem, you are doing this with two targets instead of one. Instead of checking whether a single target is less than or greater than the current node, you check whether both targets agree on the direction. If they do, follow that direction. If they do not, you have found your answer.

2. Fork-point detection. The concept of a fork point is specific to this problem but useful to internalize. Whenever you have two paths through a tree that eventually diverge, the point of divergence is the deepest shared ancestor. In a BST, you can detect this fork purely by comparing values, without ever searching subtrees.

Edge cases to watch for

• p is an ancestor of q (or vice versa): If p=2 and q=4 in our example tree, the algorithm lands on node 2 because p.val equals root.val. The else branch fires, and 2 is returned. Correct, because a node is its own descendant.
• p and q are the same node: The first comparison will hit the else branch immediately since neither "both less" nor "both greater" can be true. The current node is returned.
• p and q are in opposite subtrees of the root: The root itself is the LCA. The algorithm returns on the very first iteration.
• Skewed tree (all left children or all right children): The algorithm degrades to O(n) time, walking the entire height. This is the worst case, but O(1) space is still maintained.
• p and q are adjacent (parent and child): The parent node is the LCA. The algorithm finds it when it reaches the parent and the values stop agreeing on direction.

From understanding to recall

You just saw a clean iterative solution that leverages the BST property to find the LCA in O(h) time with O(1) space. The logic is simple: walk down, go left if both are smaller, go right if both are larger, stop when they split.

But simple does not mean memorable. Under interview pressure, will you remember to check both values against the current node? Will you remember that the else case covers the "one equals current" scenario too? Or will you start writing the general O(n) post-order DFS and waste precious minutes on an approach that ignores the BST constraint?

Spaced repetition turns understanding into reflex. You practice writing this solution from scratch at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the fork-point detection pattern until it becomes automatic.

The BST-guided search pattern appears in many problems. Drilling it here means you will recognize it instantly in validate BST, kth smallest element, and BST iterator problems. One pattern, many applications.

Related posts

• Lowest Common Ancestor of a Binary Tree - The general version that uses post-order DFS, useful for comparing how much the BST property simplifies things
• Validate Binary Search Tree - Another problem that exploits the BST invariant, passing value bounds downward instead of searching for a fork
• Kth Smallest Element in a BST - Uses BST-guided inorder traversal to find the kth element, another application of the sorted structure