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, 4) = 2      (a node can be its own ancestor)

To put this in plain English: you are given a tree where for any node, all values on its left are strictly smaller and all values on its right are strictly larger. You need to find the lowest (deepest) node that connects two given nodes, p and q.

Constraints to Keep in Mind:

• 2 <= Number of nodes in the tree <= 10^5
• -10^9 <= Node.val <= 10^9
• All Node.val are unique.
• p != q
• p and q will exist in the BST.

The Brute Force Approach

If you didn't know this was a Binary Search Tree (and treated it like a regular binary tree), you could find the LCA by finding the path from the root to p and the path from the root to q.

• How it works: You run a Depth-First Search (DFS) to find p and store its path (e.g., [6, 2]). Then you run DFS to find q and store its path (e.g., [6, 2, 4]). Finally, you compare the two paths from the start and find the last common node (which is 2).
• Why it's too slow (and uses too much space): Finding the paths requires traversing the tree, taking O(n) time in the worst case, and storing the paths takes O(n) extra memory. We can do much better by using the BST properties to avoid storing paths entirely.

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;
  }
}

Code Walkthrough

1. node = root: Start our search at the top of the tree.
2. while node:: We iterate downwards. Because p and q are guaranteed to exist, this loop will eventually return a value and won't just fall off the tree.
3. if p.val < node.val and q.val < node.val:: Check if both targets are strictly smaller than the current node. If they are, they both must be in the left subtree.
4. node = node.left: Move down to the left child and repeat.
5. elif p.val > node.val and q.val > node.val:: Check if both targets are strictly larger. If they are, they both must be in the right subtree.
6. node = node.right: Move down to the right child and repeat.
7. else:: If neither of the above is true, it means either:
   • p and q are on opposite sides of node (one is smaller, one is larger), making node the split point (the LCA).
   • One of the targets is EXACTLY node.val (meaning the other is a descendant), making node the LCA.
8. return node: We found the LCA, return it immediately.

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.

Step	Current node	p=2, q=8	Action
1	6	2 < 6, but 8 > 6	They straddle (else branch). Return 6. ✓

LCA(3, 5).

Step	Current node	p=3, q=5	Action
1	6	3 < 6 and 5 < 6	Both smaller. Go left. node = 2.
2	2	3 > 2 and 5 > 2	Both larger. Go right. node = 4.
3	4	3 < 4, but 5 > 4	They straddle (else branch). Return 4. ✓

Complexity

• Time Complexity: O(h), where h is the height of the tree. We visit at most one node per level. On a balanced tree this is O(\log n). In the worst-case (a completely unbalanced, line-like tree), it degrades to O(n).
• Space Complexity: O(1) extra space. We only use a single node pointer to traverse. If we had written it recursively, it would be O(h) space due to the call stack.

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.