4.14.7 — Lowest Common Ancestor of a Binary Search Tree

LeetCode 235 · Medium · ★ Blind 75

The problem

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

        6
      /   \
     2     8
    / \   / \
   0   4 7   9
      / \
     3   5

LCA(2, 8) = 6
LCA(2, 4) = 2      (a node can be its own ancestor)

The pattern

In a general binary tree this needs a full search. In a search tree it needs almost nothing, because the ordering tells you which way to go.

Stand at a node and compare both targets against it:

• Both smaller — both are in the left subtree, so the answer is down there. Go left.
• Both larger — go right.
• Anything else — this node is the answer.

That last case covers everything interesting: one target on each side, or one of the targets being this node. In either situation, no node further down can have both as descendants, so this is the lowest one that does. This is the split point, and finding it is the whole algorithm.

The solution

Python

class Solution:
    def lowestCommonAncestor(self, root, p, q):
        node = root
        while node:
            if p.val < node.val and q.val < node.val:
                node = node.left
            elif p.val > node.val and q.val > node.val:
                node = node.right
            else:
                return node

TypeScript

function lowestCommonAncestor(root: TreeNode, p: TreeNode, q: TreeNode): TreeNode {
  let node: TreeNode = root;
  while (true) {
    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;
  }
}

Iterative, and O(1) space. There is nothing to remember — the walk never needs to come back up, because the ordering makes each decision final. Recursion works too and costs O(h) stack for no benefit.

No null check is needed inside the loop, because the problem promises both nodes exist in the tree, so the walk always terminates at the split point before running out of nodes. In code you did not control, you would guard it.

The else is doing more work than it looks. It fires when the two values straddle the current node, and also when one of them equals it. Both mean stop here.

Trace

LCA(2, 8) on the tree above.

At node 6: 2 < 6 but 8 > 6, so they straddle. Return 6.

LCA(3, 5).

At node 6: both smaller → go left to 2. At node 2: both larger → go right to 4. At node 4: 3 < 4 and 5 > 4, straddle → return 4. ✓

Complexity

O(h) time — one step per level, so O(\log n) on a balanced tree and O(n) on a degenerate one. O(1) space.

The general binary tree version

LeetCode 236 removes the search-tree property, so the ordering trick is gone and you must search.

def lowestCommonAncestor(self, root, p, q):
    if not root or root is p or root is q:
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root            # found one on each side → this is the LCA
    return left or right        # both on one side, or neither

Read what the return value means: "if either target is anywhere in this subtree, return the shallowest evidence of it." If both children return something, the targets are on opposite sides and this node is the meeting point. If only one child returns something, pass it upward.

O(n) time, O(h) space. Knowing both versions and being able to say what changed is the interview answer — the BST version is O(h) and O(1) space because the ordering removes the search.

Where this goes next

• LCA of a Binary Tree — above.
• LCA with parent pointers — walk both nodes up to the root and find where the two paths merge. That is the same problem as finding where two linked lists intersect.
• LCA with many queries — precompute with binary lifting or an Euler tour plus a sparse table, then answer each query in O(\log n) or O(1). Worth naming if asked about scale.

The rule: in a search tree, the ordering replaces searching. Any problem that would need a traversal in a general tree becomes a single root-to-leaf walk.

What the interviewer will push on

"Why does the split point work?" Below it, both targets are on the same side, so no deeper node can have both.

"What if one node is an ancestor of the other?" The else branch fires when one target equals the current node, and returns it. Correct — a node is its own descendant.

"What changes without the BST property?" The recursive search, O(n) instead of O(h).

"What if the nodes might not be in the tree?" The general version would return a node even if only one target is present, so you would need to verify both exist first, or return a count alongside the node.

One thing to volunteer: say the ordering is doing the searching for you. That framing is what makes the BST version obvious rather than memorised.

Next: 4.14.8 Binary Tree Level Order Traversal — the first BFS problem, and the template for four more.