Lowest Common Ancestor: BST Walk vs Binary Tree Recursion

"Find the lowest common ancestor of two nodes" comes in two versions that look identical on the page. In one, the tree is a binary search tree, and the answer is a short loop that never searches. In the other, it is any binary tree, and the answer is a recursion that has to look everywhere. Knowing which version you have been handed is half the question.

The problem it solves

The lowest common ancestor (LCA) of nodes a and b is the deepest node that has both of them in its subtree. A node counts as its own descendant, so if a is an ancestor of b, the answer is a.

It shows up wherever a hierarchy needs a meeting point: the nearest shared folder of two files, the most specific category that covers two products, the branch point of two commits in a version history, or the distance between two nodes in a tree, which is depth(a) + depth(b) - 2 * depth(lca).

The intuition

On a BST, the values tell you where to go. Start at the root. If both targets are smaller than the current value, both live in the left subtree, so step left. If both are larger, step right. Otherwise they are on different sides of this node — or one of them is this node — and that is the split point. Nothing below it can contain both, and it contains both, so it is the LCA. One step per level, no backtracking.

On a general binary tree, values say nothing about position. So ask each subtree a question and combine the answers bottom-up. The recursion returns a node when it has found something in that subtree: a target, or an ancestor already found below. At each node:

• If the node itself is a target, return it — whatever is below, this node is the highest point of interest on this branch.
• Otherwise, recurse into both children. If both sides return something, one target is on each side, so this node is the LCA.
• If only one side returns something, pass it up unchanged.

The value that reaches the root is the answer.

Watch it run

The animation runs the BST walk three times on the tree 6 → (2 → 0, 4), (8 → 7, 9). For lca(0, 4), both targets are below 6, so the walk steps left and fades the whole right side; at 2 they split. For lca(2, 8) they split at the root immediately. For lca(7, 9) the walk steps right once and stops at 8.

The code

Both versions, plus the one input that trips the recursive version:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def lca_bst(node, a, b):               # uses the ordering: one path, no search
    while node:
        if a < node.val and b < node.val:
            node = node.left           # both smaller: go left together
        elif a > node.val and b > node.val:
            node = node.right          # both larger: go right together
        else:
            return node.val            # they split here (or one of them is here)
    return None

def lca_tree(node, a, b):              # any binary tree, values unique
    if node is None or node.val in (a, b):
        return node
    left = lca_tree(node.left, a, b)
    right = lca_tree(node.right, a, b)
    if left and right:                 # one target on each side: this is it
        return node
    return left or right               # pass up whichever side found something

root = Node(6, Node(2, Node(0), Node(4)), Node(8, Node(7), Node(9)))
print(lca_bst(root, 0, 4), lca_bst(root, 2, 8), lca_bst(root, 7, 9))   # 2 6 8
print(lca_tree(root, 0, 4).val, lca_tree(root, 4, 7).val)               # 2 6
print(lca_tree(root, 0, 99).val)       # 0  -- 99 is not in the tree at all

The brute force for testing uses the definition from the other end: record every node's parent, collect all ancestors of a, then climb from b until you hit one of them. Both versions are compared with it on 3,000 random BSTs, and the recursive version also on random trees of any shape holding the same values. The last counter runs the BST walk on those unordered trees:

import random

def brute(root, a, b):                 # walk up from b until we meet a's line
    parent, stack = {root.val: None}, [root]
    while stack:
        n = stack.pop()
        for child in (n.left, n.right):
            if child:
                parent[child.val] = n.val
                stack.append(child)
    line, v = set(), a
    while v is not None:
        line.add(v)
        v = parent[v]
    v = b
    while v not in line:
        v = parent[v]
    return v

def random_tree(vals):                 # any shape, unique values, no order
    if not vals:
        return None
    k = random.randrange(len(vals))
    return Node(vals[0], random_tree(vals[1:k + 1]), random_tree(vals[k + 1:]))

def insert(node, v):
    if node is None:
        return Node(v)
    if v < node.val:
        node.left = insert(node.left, v)
    else:
        node.right = insert(node.right, v)
    return node

random.seed(8)
ok_bst = ok_tree = True
bst_on_any = 0
for _ in range(3000):
    vals = random.sample(range(100), random.randint(1, 15))
    bst = None
    for v in vals:                     # a real BST, built by insertion
        bst = insert(bst, v)
    a, b = random.choice(vals), random.choice(vals)
    ok_bst &= lca_bst(bst, a, b) == brute(bst, a, b)
    ok_tree &= lca_tree(bst, a, b).val == brute(bst, a, b)

    shuffled = random.sample(vals, len(vals))
    tree = random_tree(shuffled)       # same values, no ordering promise
    ok_tree &= lca_tree(tree, a, b).val == brute(tree, a, b)
    bst_on_any += lca_bst(tree, a, b) != brute(tree, a, b)
print(ok_bst, ok_tree, bst_on_any)     # True True 1543

Both versions agree with the brute force everywhere they are meant to work. The BST walk, run on trees without the ordering, was wrong 1,543 times out of 3,000 — roughly half. It does not crash or complain; it confidently returns a wrong node.

The complexity

• BST walk: one step per level, O(h) time, O(1) extra space because it is a loop. h is about log n for a balanced tree and n for a chain.
• General recursion: it may have to visit every node before it finds both targets, so O(n) time, and O(h) stack space for the recursion.
• Brute force with parent pointers: O(n) to build the map, then O(h) per query. If there are many queries on one fixed tree, precomputing ancestors (for example with binary lifting) answers each in O(log n) after O(n log n) preparation.

Where it goes wrong

• Using the BST walk on a plain binary tree. Shown above: about half the answers were wrong on these random trees. Ask whether the tree is a BST before choosing.
• A target that is missing. The recursive version returns the first target it finds, so lca_tree(root, 0, 99) returns 0 even though 99 is not in the tree. If existence is not guaranteed, count how many targets were actually found and return nothing unless it is two.
• Duplicate values. Both versions compare values, so equal values make "which node?" ambiguous. Compare node identities instead when duplicates are allowed.
• Forgetting that a node is its own ancestor. lca(2, 0) on the example tree is 2. Both versions handle it; a hand-rolled one often does not.

How to say it in an interview

"If it's a BST, I start at the root and move left while both values are smaller and right while both are larger; the first node where they split is the answer. That's O(h) time and constant space. If it's a general binary tree, I recurse: a subtree returns a target it contains or the LCA it already found. If both children return something, the current node is the LCA. That's O(n) time, and it assumes both nodes exist — I'd add a count if they might not."

The ordering rule the first version relies on is the same one checked in validate a BST.