Lowest Common Ancestor of a BST: A Step-by-Step Interview Walkthrough

May 22

9 min read

Lowest Common Ancestor of a BST is a problem that interviewers use to test a specific kind of reading comprehension: did the candidate notice they were handed a BST, or did they treat it as a generic binary tree? The version of this problem for any binary tree is genuinely hard — you need to track paths, return ancestor candidates from recursive calls, and handle several non-obvious cases. The BST version is genuinely easy if you exploit the BST property. The signal is whether you treat the data structure's invariants as algorithmic information rather than incidental detail.

Finding common ancestors in ordered hierarchical data is a routine operation in version control systems (finding the merge base of two commits when the DAG is augmented with ordering hints), permission systems built on hierarchical roles, file system path resolution, and any application where you need to find the narrowest scope that contains two ordered items. Whenever the hierarchy itself encodes ordering — like in interval trees, segment trees, or B+ trees with key-range partitioning — the same comparison-based descent applies.

Problem Statement

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes p and q.

The lowest common ancestor is defined as the lowest node in the tree that has both p and q as descendants (where a node can be a descendant of itself).

You may assume:

Both p and q exist in the BST.
All node values are unique.

Example:

For p = 2, q = 8, the LCA is 6. For p = 2, q = 4, the LCA is 2.

1. Clarify Requirements Before Jumping Into Code

Before writing a single line, we should restate the problem in our own words and ask the kinds of questions that would change our approach.

Input: the root of a BST and two nodes p and q.

Output: the node that is the lowest common ancestor of p and q.

Details to clarify:

Are p and q guaranteed to be in the tree? Yes — we don't need to handle missing nodes.
Are values unique? Yes — no duplicates, so values uniquely identify nodes.
Can a node be an ancestor of itself? Yes — that's part of the LCA definition. If p is an ancestor of q, then p is the LCA.
Does it matter whether p and q are distinct? They're given as distinct nodes, but the algorithm works even if they happen to be the same.

The thing to flag is the BST in the problem name. It's not a general binary tree — it's a BST, which means values are ordered. That single word should change our approach entirely.

2. Identify the Category of the Question

A few signals jump out:

The input is a BST, not just any tree.
The decision at each node is: do I go left, right, or stop here?
The decision depends on comparing values, not traversing structure.

That combination — BST input, directional decision, value comparison — points to a particular pattern: comparison-based descent. Same family as searching for a value in a BST, range queries, predecessor/successor lookups, and validating a BST with bounds. Every problem in this family follows the same shape: start at the root, compare some value(s) to the current node, and use the comparison to pick a direction.

3. Brute Force Solution

Let's start with the approach that works for any binary tree, ignoring the BST property:

Find the path from the root to p (a list of nodes).
Find the path from the root to q.
Walk both paths from the root, finding the last common node before they diverge. That's the LCA.

List<TreeNode> pathToP = findPath(root, p);
List<TreeNode> pathToQ = findPath(root, q);
TreeNode lca = root;
for (int i = 0; i < Math.min(pathToP.size(), pathToQ.size()); i++) {
    if (pathToP.get(i) != pathToQ.get(i)) break;
    lca = pathToP.get(i);
}
return lca;

This is correct, and it works on any binary tree. But notice what it's doing: it walks the tree twice, builds two lists in memory, then walks the lists in parallel to find the divergence point. Total work is O(n) time and O(n) space — fine for a general tree, but suspicious for a BST.

The brute force teaches us the key question: what is the BST giving us that this algorithm throws away? It builds explicit paths because it doesn't trust the tree to tell it which direction to go. In a BST, value comparisons already tell us which direction p or q lies in. We don't need to record paths — we can re-derive direction on the fly.

4. Brainstorm More Solutions

Step 1: What does the BST property tell us about ancestors?

Let's think carefully about where the LCA can be, given the BST property. Pick any two nodes p and q and stand at the root. The BST tells us:

Every value less than the root lives in the left subtree.
Every value greater than the root lives in the right subtree.

Let's enumerate all the options for how p could relate to the root. p could be:

Smaller than the root (in the left subtree), or
Larger than the root (in the right subtree), or
Equal to the root (it is the root).

The same applies to q.

There are really only a handful of combinations. Let's list them out:

p and q could both be smaller than the root. That means both are in the left subtree. The LCA is thus also somewhere in the left subtree — it can't be the root, because the root is too high.
p and q could both be larger than the root. That means both are in the right subtree, so the LCA is somewhere in the right subtree.
One could be smaller and the other one larger (or one equals the root). This means they live in different subtrees of the root. The root is the closest node that has both as descendants — anything lower would be in one subtree and would lose access to the other.

That third case is the key. The moment p and q are on different sides of the current node, the current node is the LCA. Anything deeper would be committed to one side and would lose the other.

Step 2: Translate the cases into an algorithm

The three cases above give us a simple decision rule:

If both values are smaller than the current node → go left.
If both values are larger than the current node → go right.
Otherwise → return the current node.

That's the algorithm. No path tracking, no bookkeeping. Just compare, descend, and stop when the paths split.

node = root
while true:
    if p.val < node.val and q.val < node.val:
        node = node.left
    else if p.val > node.val and q.val > node.val:
        node = node.right
    else:
        return node

A subtle detail in the "otherwise" branch: it covers three sub-cases at once.

p.val < node.val and q.val > node.val — they're on opposite sides; current node is the LCA.
p.val > node.val and q.val < node.val — symmetric; same conclusion.
One of them equals node.val — that node is p or q, and the other lies in one of its subtrees. Since a node is its own ancestor, node is the LCA.

All three resolve to "return the current node." The case split is cleaner than it looks because the BST property collapses the messy general-tree LCA logic into a single decision.

Step 3: Why no recursion is needed

Notice something about the algorithm: at each step, we either return or move strictly downward. We never need information from a subtree to inform a decision at an ancestor. That's different from the general-tree LCA, where a recursive call might return an ancestor candidate that the parent has to interpret.

When you don't need information flowing back up, recursion is overkill. Iteration is fine and uses O(1) auxiliary space. We can use recursion too — it's a stylistic choice — but the iterative version is strictly better in space.

Compare:

// Recursive — clean but uses O(h) stack space
public TreeNode lca(TreeNode node, TreeNode p, TreeNode q) {
    if (p.val < node.val && q.val < node.val) return lca(node.left, p, q);
    if (p.val > node.val && q.val > node.val) return lca(node.right, p, q);
    return node;
}

// Iterative — same logic, O(1) auxiliary space
public TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
    while (root != null) {
        if (p.val < root.val && q.val < root.val) root = root.left;
        else if (p.val > root.val && q.val > root.val) root = root.right;
        else return root;
    }
    return null;
}

Both are O(h) time, but the iterative version is O(1) space versus O(h) stack frames for the recursive one. For deeply skewed trees, the iterative version is safer.

Step 4: Complexity

The algorithm descends at most one level per iteration and does O(1) work per level (two comparisons, one assignment). The total number of iterations is bounded by the height of the tree, h. So total time is O(h).

For a balanced BST, h = O(log n). For a skewed BST, h = O(n) worst case. Either way, we never visit more than one node per level, which is fundamentally better than the brute force's O(n) traversal-twice approach.

Auxiliary space is O(1) for the iterative version and O(h) for the recursive version. The brute force used O(n) space for the two paths. So we've improved on both axes by leaning on the BST property.

5. Discuss Trade-Offs Between Solutions

Approach	Time	Space	When I'd use it
Path comparison (works on any tree)	O(n)	O(n)	If the input weren't a BST — but here, it ignores guaranteed structure
Recursive BST descent	O(h)	O(h) stack	Clean and expressive; fine for balanced trees
Iterative BST descent	O(h)	O(1)	My default interview answer — optimal time and space

The iterative version is the right answer for this problem. It's no harder to write than the recursive version, and it doesn't carry the stack overhead.

6. Pseudocode

node = root
while node is not null:
    if p.val < node.val and q.val < node.val:
        node = node.left
    else if p.val > node.val and q.val > node.val:
        node = node.right
    else:
        return node
return null  # unreachable given the problem's guarantees

7. Edge Cases

Things to verify before claiming we're done:

One of p or q is the root → first iteration hits the "otherwise" branch, returns the root. ✓
p is an ancestor of q (or vice versa) → we descend until we hit p, at which point q.val falls in p's subtree, triggering the "otherwise" branch. Returns p. ✓
p and q are siblings → we descend to their parent, where one is smaller and one is larger. Returns the parent. ✓
p == q → first iteration's "otherwise" branch returns that node (a node is its own LCA).
Completely skewed tree → algorithm still works; it just descends a long single-direction chain. The iterative version is safe even with O(n) height.
p and q on opposite ends of the tree → the root is the LCA, returned on the first iteration.

The comparison logic naturally handles all these cases — no special branches needed. That's the sign of a well-fitted algorithm.

8. Full Code

public class LowestCommonAncestorBST {

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int val) {
            this.val = val;
        }
    }

    // Iterative BST descent 
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while (root != null) {
            if (p.val < root.val && q.val < root.val) {
                // Both targets are smaller — 
                // LCA is in the left subtree
                root = root.left;
            } else if (p.val > root.val && q.val > root.val) {
                // Both targets are larger — 
                // LCA is in the right subtree
                root = root.right;
            } else {
                // The targets split here (or one IS this node) — 
                // this is the LCA
                return root;
            }
        }
        return null;  // unreachable given the problem's guarantees
    }

9. Test the Code

TreeNode root = new TreeNode(6);
root.left = new TreeNode(2);
root.right = new TreeNode(8);
root.left.left = new TreeNode(0);
root.left.right = new TreeNode(4);
root.left.right.left = new TreeNode(3);
root.left.right.right = new TreeNode(5);
root.right.left = new TreeNode(7);
root.right.right = new TreeNode(9);

// Split at root: 2 and 8 are on opposite sides of 6
System.out.println(lowestCommonAncestor(root, root.left, root.right).val);  // 6

// One node is an ancestor of the other: 2 is ancestor of 4
System.out.println(lowestCommonAncestor(root, root.left, root.left.right).val);  // 2

// Both in deeper subtree: 3 and 5 share parent 4
System.out.println(lowestCommonAncestor(root, root.left.right.left, root.left.right.right).val);  // 4

// Root is one of the nodes: 6 and 4
System.out.println(lowestCommonAncestor(root, root, root.left.right).val);  // 6

// Same node twice: LCA is itself
System.out.println(lowestCommonAncestor(root, root.left, root.left).val);  // 2

These hit the meaningful cases: split at the root, ancestor-descendant pairs, deeper subtree LCAs, the root itself being one of the queried nodes, and the degenerate case of the same node twice.

10. Key Lessons

When a problem gives you a specific data structure, ask what that structure guarantees that a generic structure wouldn't. "Binary tree" gives you nothing about value ordering. "Binary search tree" gives you direction for free through value comparisons. Spotting the difference is most of the work.
Enumerating all the different ways that your inputs relate to each other given the problem's constraints is a good place to start when you're trying to build your solution.
The LCA in a BST is wherever the two target values split — first node from the root where one target is on the left and the other is on the right (or one equals the node itself). That divergence point captures "lowest common ancestor" exactly.
When an algorithm never needs information flowing back up from subtrees, recursion is overkill. Iterative descent uses O(1) auxiliary space and is just as readable.
The "or one equals the current node" case is what makes a node its own ancestor work. Always check whether the problem's definition allows this — for LCA, it usually does, and the algorithm gets simpler when you accept it.
The general-tree version of this problem (which we mention briefly in the brute force) is much harder. Knowing both versions, and knowing why the BST version is easier, helps you respond intelligently if the interviewer follows up with "now solve it without the BST property."

Good Luck and Happy Coding!