Lowest Common Ancestor of a Binary Search Tree

1. Problem & Core Objective

Given a BST and two nodes p and q, find their lowest common ancestor — the deepest node that has both as descendants. A node counts as a descendant of itself.

        6
      /   \
     2     8         LCA(2, 8) = 6
    / \   / \        LCA(2, 4) = 2   (a node is its own descendant)
   0   4 7   9       LCA(7, 9) = 8
      / \
     3   5

Constraints: 2 <= nodes <= 10^5 · all values unique · p and q both exist in the tree

What's actually being tested: whether you use the BST property. The general-tree LCA is O(n) and requires a full search; in a BST it's O(h) with no search at all — you walk straight down. Solving this with the general algorithm gets the right answer and misses the entire point.

2. First-Principles Thought Process

What the BST property buys you

In a BST, every node's value separates its two subtrees: everything on the left is smaller, everything on the right is larger. So at any node you can tell which side a target value lives on by a single comparison — no searching.

Where must the LCA be?

Compare p and q against the current node:

• Both smaller → both live in the left subtree → the LCA is in there too → go left.
• Both larger → both live in the right subtree → go right.
• Otherwise → they split here: one is <= this node and the other is >=. This node is the ancestor of both, and no node deeper can be — going either way loses one of them.

Why the first split is the lowest

Walking down, every node before the split has both targets on the same side, so it's an ancestor but not the lowest. At the split, the two targets diverge into different subtrees. Any deeper node lies entirely within one of those subtrees and so cannot contain both.

So the first node where they split is the lowest common ancestor. There's no need to continue, and no need to backtrack.

The case people forget

If p is an ancestor of q, the answer is p itself — because a node is its own descendant. The split condition handles this automatically: when the current node is p, the comparison p.val < node.val is false, so it isn't "both smaller", and the else branch returns it. No special case needed, but worth checking rather than assuming.

3. Solution Paths

Approach 1 — General binary-tree LCA (brute force here)

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root;

    TreeNode left  = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);

    if (left != null && right != null) return root;   // found on both sides — split here
    return (left != null) ? left : right;
}

The standard algorithm for an arbitrary binary tree. It works on a BST, because a BST is a binary tree.

• Time O(n) · Space O(h) stack

Counter-questions on this approach

⭐ "This is correct. Why isn't it the answer?"

Because it ignores the BST property entirely — it would work identically on a tree with values in random order. It has to search the whole tree to locate p and q, which is O(n).

The BST lets me know which way to go from a single comparison, so I never search: I walk straight down one root-to-node path. That's O(h), which is O(log n) on a balanced tree. At n = 10^5 that's roughly 17 steps instead of 100,000.

Being handed a BST and not using its ordering is the mistake the question is designed to catch.

⭐ "Explain how this one works, since it's worth knowing."

It returns "the LCA if found in this subtree, otherwise whichever of p/q was found, otherwise null". If both children return non-null, the two targets are in different subtrees, so the current node is the split point. If only one side returns non-null, that result bubbles up.

The subtle part is root == p || root == q returning immediately: it encodes "a node is its own descendant", which is why an ancestor-descendant pair works without extra handling.

"When would you actually use this one?"

Question-8-style trees with no ordering, or LeetCode 236 — the general-tree version. It's the right tool there; it's just the wrong tool when ordering is available.

Approach 2 — Walk down using the ordering (optimal)

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;
        else if (p.val > node.val && q.val > node.val) node = node.right;
        else return node;                               // they split here
    }
    return null;                                        // unreachable given the constraints
}

Trace — LCA(2, 8) in the example tree:

Trace — LCA(2, 4):

• Time O(h) · Space O(1) — iterative, no stack

Counter-questions on this approach

⭐ "Why can you stop at the first split? Don't you need to check deeper?"

No. At the split, p is in one subtree and q is in the other. Any node strictly below the current one lies entirely inside one of those two subtrees, so it can contain at most one of the targets — it cannot be a common ancestor at all, let alone a lower one.

And every node above the split has both on the same side, so it's an ancestor but not the lowest. So the first split is exactly the LCA.

⭐ "What if p is an ancestor of q?"

Then the answer is p, since a node is its own descendant — and the code returns it without a special case. When the walk reaches p, the test p.val < node.val is comparing p.val with itself and is false, so it isn't "both smaller"; similarly for "both larger". So it falls into the else and returns p.

Worth tracing explicitly rather than trusting it: LCA(2, 4) above is exactly this case.

"Why is this O(1) space when the recursive version is O(h)?"

Because it's a single downward walk with no branching, so there's nothing to remember — a loop suffices. The general algorithm must explore both subtrees and combine results, which requires a stack. The BST property doesn't just save time; it removes the need to backtrack at all.

"Would a recursive version be equally good?"

It's equally correct and reads fine, but it's O(h) stack for a tail-recursive walk the JVM won't optimize. Since the iterative form is barely longer, I'd take the O(1).

"What if p or q weren't in the tree?"

The walk would run off the bottom and return null — but it can also return a wrong node. If p exists and q doesn't, it may return an ancestor of p as though both were found. To be safe you'd verify both exist first, at O(h) each. The constraints guarantee presence, so I'd note the assumption rather than pay for it.

"Does it matter if p.val > q.val?"

No. The conditions are symmetric in p and q — both use the same comparison against the node — so the order of the arguments is irrelevant.

Comparison

4. Why the Optimal Wins

The general algorithm searches; the BST version navigates. That's the whole difference, and it's a factor of n / log n — at 10^5 nodes, roughly 17 comparisons versus 100,000 visits.

It also drops to O(1) space, because a BST walk never backtracks. Every step is decided by one comparison and is final.

The framing worth keeping:

In a BST, a comparison at a node tells you which subtree a value is in. That turns searching into navigating — and the LCA is simply the first node where the two targets disagree about which way to go.

The general algorithm is still worth knowing cold, because LeetCode 236 asks for exactly it — and the follow-up here is usually "now do it without the BST property".

5. Java Prerequisites

The BST descent

if (target < node.val)      node = node.left;
else if (target > node.val) node = node.right;
else                        /* found */;

Value vs reference comparison. This solution compares p.val against node.val, not p == node. That's fine because BST values are unique — if they weren't, value comparison would be ambiguous and you'd need reference identity plus a different algorithm.

Iterative beats recursive for pure descents. Any recursion whose recursive call is the last thing it does — and that doesn't combine results — is a loop in disguise. The JVM won't eliminate the frames, so write the loop.

The general LCA return convention: "the LCA if found here, else whichever target was found, else null" — a single return value carrying three meanings, much like the −1 sentinel in question 4.

6. Interview Communication Guide

Clarifying questions: Is it guaranteed to be a valid BST (yes — it's the whole point)? Are values unique (yes; it justifies comparing values rather than references)? Are p and q guaranteed present (yes)? Does a node count as its own ancestor (yes — it decides the ancestor-descendant case)?

The pitch

"The BST property means a single comparison at a node tells me which subtree a value lives in. So I never have to search — I navigate.

Starting at the root: if both p and q are smaller than the current node, both are in the left subtree, so their LCA is too — go left. If both are larger, go right. Otherwise they split here, and this node is the answer.

The first split is the lowest common ancestor, because below it p and q are in different subtrees — any deeper node sits entirely inside one of them and can contain at most one target. And every node above has both on the same side, so it's an ancestor but not the lowest.

The ancestor-descendant case falls out without special handling: if the current node is p, then p.val < node.val is false, so it isn't 'both smaller', and the else branch returns it — which is right, since a node is its own descendant.

O(h) time, O(1) space, because the walk never backtracks.

I'd contrast that with the general binary-tree LCA, which recurses both subtrees and returns the node where two non-null results meet. That's O(n) time and O(h) stack, and it's the correct answer when there's no ordering — LeetCode 236. Here, not using the ordering would be leaving the entire point on the table."

Edge cases to volunteer:

Name LCA(2, 4). The ancestor-descendant case is the one that breaks implementations which insist the LCA must be strictly above both nodes.

7. Follow-Up Questions — Modified Constraints

⭐ "Do it for a general binary tree with no ordering."

LeetCode 236 — the first approach above. Recurse both subtrees; if both return non-null, the current node is the split and therefore the LCA; otherwise propagate whichever side found something. O(n) time, O(h) space. Worth having ready, because it's the natural follow-up to this question.

⭐ "What if p or q might NOT be in the tree?"

Both algorithms can then return a plausible but wrong node. The fix is to verify presence — O(h) each in a BST — or, for the general version, to return a count alongside the node and only accept a result where both targets were actually found. Worth raising unprompted, since the constraint quietly removes a real problem.

"Find the LCA of k nodes rather than two."

In a BST, take the minimum and maximum of the k values and run this algorithm on those two — every other value lies between them, so the LCA of the extremes is the LCA of all. Neat, and O(h) still. In a general tree you'd fold the pairwise LCA across the set.

"What if nodes had parent pointers?"

Walk up from both nodes to collect their depths, advance the deeper one until they're level, then step up together until they meet. O(h) time, O(1) space, and it needs no ordering — the same technique as finding the intersection of two linked lists.

"Answer many LCA queries on a static tree."

Preprocess. Binary lifting gives O(n log n) preprocessing and O(log n) per query; the Euler tour plus sparse table reduction gives O(n log n) preprocessing and O(1) per query. Worth naming once query volume is the constraint rather than a single lookup.

"What if the BST contained duplicates?"

Comparing values becomes ambiguous — you can't tell which of two equal nodes you're looking for. You'd need reference identity, which the descent can't use, so you'd fall back to the general O(n) algorithm. This is exactly why the uniqueness constraint is there.