Module 18 · Tree BFS, Binary Search Trees, and Tries

177. Lowest Common Ancestor in BST

Bridge · Download this solution · All solutions and shared helpers

Problem

Given a strict BST and two values p and q that are both present, return the node object of their lowest common ancestor. A node is its own ancestor, and p may equal q. Leave the tree unchanged. Presence is a precondition, not an extra search performed here.

Examples

Example 1

lca_bst(build_tree([6,2,8,0,4,7,9]),2,8).val
=> 6

The targets first split at the root.

Example 2

lca_bst(build_tree([6,2,8,0,4]),2,4).val
=> 2

A target node can itself be the ancestor.

Example 3

lca_bst(build_tree([2,1,3]),3,3).val
=> 3

Equal targets have that node as their lowest ancestor.

Reveal the worked solution and reasoning

Why this mechanism works

If both target values are smaller than the current value, their common ancestor must remain in the left subtree; the symmetric rule holds on the right. Otherwise the targets split across the current node, or one equals it. That is the first point where neither single child can contain both.

State and boundaries

The current root remains an ancestor candidate whose subtree contains both target values.

Protocol

While the current node exists, compare both targets with its value.
Move left if both are smaller.
Move right if both are larger.
Otherwise return the current node.

Visualization

at 6: targets 2 and 8 split -> return 6
at 6: targets 2 and 4 both smaller -> move left
at 2: one target equals current -> return 2

Python implementation

from structures import build_tree

def lca_bst(root, p, q):
    while root is not None:
        if p < root.val and q < root.val:
            root = root.left
        elif p > root.val and q > root.val:
            root = root.right
        else:
            return root
    return None

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

lca_bst(build_tree([6,2,8,0,4,7,9]),2,8).val

L4 lca_bst: while root is not None:
root=N1(val=6,left=N2,right=N3); p=2; q=8

Result: 6. The targets first split at the root.

lca_bst(build_tree([6,2,8,0,4]),2,4).val

L4 lca_bst: while root is not None:
root=N1(val=6,left=N2,right=N3); p=2; q=4

L6 lca_bst: root = root.left
root=N2(val=2,left=N4,right=N5); p=2; q=4

Result: 2. A target node can itself be the ancestor.

Why the solution is correct

Each same-side move retains both targets and discards ancestors that cannot be lowest. At a split, no child subtree contains both targets; when one target equals the current node, no descendant can be its ancestor. The returned node is therefore the lowest common ancestor.

Time and space

O(h) time and O(1) auxiliary space; O(n) time in a skewed BST.

Common mistakes

Moving on only one target's comparison can discard the other target. Without the presence precondition, a split point need not be an ancestor of existing target nodes.

Reasoning card

State: The current root remains an ancestor candidate whose subtree contains both target values.

Invariant: Current node remains an ancestor candidate for both targets.

Decision to rehearse: Move left/right only when both targets lie on the same side.

Finish: Otherwise return the current node

Transfer exercise

Support possibly absent targets by validating membership, and state the extra traversal cost.