DSA Lowest Common Ancestor

The problem

The lowest common ancestor of two nodes is the deepest node whose subtree contains both of them. A subtree is a node together with everything below it. Deepest means furthest from the root.

This tree is a general binary tree. Its values follow no ordering rule, so no search can rule out a whole side early. Both targets are present in the tree in every case below.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

for a, b, expected in [(9, 2, 3), (9, 8, 7), (1, 8, 5), (3, 2, 3), (9, 1, 7)]:
    print("targets", a, "and", b, "- lowest common ancestor:", expected)

Read one row at a time. The pair 9 and 2 meets at node 3. The pair 9 and 8 meets only at the root. The pair 3 and 2 answers node 3 itself, because a node counts as its own ancestor here.

Intuition: the two root paths share a prefix

A first idea follows the path from the root down to each target. Both paths start at the root. They split apart at exactly one node, and that split point is the answer.

The paths are lists of values in root-to-target order. Their shared values form the start of both lists. The last shared value is the deepest node holding both targets below it.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def find_path(node, target, path):
    if node is None:
        return False
    path.append(node.value)
    if node.value == target:
        return True
    if find_path(node.left, target, path) or find_path(node.right, target, path):
        return True
    path.pop()
    return False

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

path_a = []
find_path(tree, 9, path_a)
path_b = []
find_path(tree, 8, path_b)
print("path to 9:", path_a)
print("path to 8:", path_b)
common = [value for value in path_a if value in path_b]
print("shared values:", common)
print("last shared value:", common[-1])

The paths share only the value 7. Node 7 is therefore the answer for this pair. Finding the paths costs a search each, and the brute force below pays much more than that.

Brute force: test every node as the ancestor

The brute force tries each node as a candidate ancestor. It collects the values of that node's whole subtree. A candidate passes when both targets appear in its collection.

The deepest passing candidate is the answer. A counter records every node scanned while collecting subtrees. The count shows how much ground the method rewalks.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def subtree_values(node, values, scans):
    if node is None:
        return
    scans[0] += 1
    values.append(node.value)
    subtree_values(node.left, values, scans)
    subtree_values(node.right, values, scans)

def collect(node, depth, nodes):
    if node is None:
        return
    nodes.append((depth, node))
    collect(node.left, depth + 1, nodes)
    collect(node.right, depth + 1, nodes)

def lca_brute(root, a, b):
    nodes = []
    collect(root, 0, nodes)
    scans = [0]
    answer = None
    best_depth = -1
    for depth, node in nodes:
        values = []
        subtree_values(node, values, scans)
        if a in values and b in values and depth > best_depth:
            best_depth = depth
            answer = node.value
    return answer, scans[0]

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

for a, b in [(9, 2), (9, 8), (1, 8), (3, 2)]:
    answer, scans = lca_brute(tree, a, b)
    print("targets", a, "and", b, "->", answer, "subtree scans:", scans)

Seven nodes produce 17 subtree scans for a single question. Every node's subtree is collected in full, even the subtrees of leaves. A bigger tree multiplies that waste.

The optimal solution: one search that reports what each side found

One recursive search returns the first target found in each subtree, and a node that receives a target from both sides is the answer. That one sentence is the whole method.

A node equal to a target returns itself at once. That early return is what makes an ancestor target work. The other target must sit below it, and the returned node is already the deepest meeting point.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def lca(node, a, b, visits):
    if node is None:
        return None
    visits[0] += 1
    if node.value == a or node.value == b:
        return node
    left = lca(node.left, a, b, visits)
    right = lca(node.right, a, b, visits)
    if left is not None and right is not None:
        return node
    if left is not None:
        return left
    return right

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

for a, b, expected in [(9, 2, 3), (9, 8, 7), (1, 8, 5), (3, 2, 3), (9, 1, 7)]:
    visits = [0]
    answer = lca(tree, a, b, visits)
    print("targets", a, "and", b, "->", answer.value,
          "expected:", expected, "match:", answer.value == expected,
          "visits:", visits[0])

All five cases from the start of the article pass. Every answer needs at most seven visits, the node count of the tree. The ancestor-target case finishes early, in five visits, because node 3 returns itself at once.

Walkthrough: targets 9 and 8, reported up the tree

The walkthrough traces the search for 9 and 8. Each line prints after a node's two sides have reported. Indentation shows depth in the tree.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def lca_traced(node, a, b, depth):
    if node is None:
        return None
    if node.value == a or node.value == b:
        print("  " * depth + "node", node.value, "is a target, return", node.value)
        return node
    left = lca_traced(node.left, a, b, depth + 1)
    right = lca_traced(node.right, a, b, depth + 1)
    left_value = left.value if left is not None else None
    right_value = right.value if right is not None else None
    if left is not None and right is not None:
        result = node
        note = "one target on each side"
    elif left is not None:
        result = left
        note = "only the left side found a target"
    elif right is not None:
        result = right
        note = "only the right side found a target"
    else:
        result = None
        note = "neither side found a target"
    print("  " * depth + "node", node.value, "- left returned", left_value,
          "- right returned", right_value, "-", note, "- return",
          result.value if result is not None else None)
    return result

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

answer = lca_traced(tree, 9, 8, 0)
print("lowest common ancestor of 9 and 8:", answer.value)

Node 3 returns 9, because its left side found a target and its right side found nothing. Node 5 returns 8 in the same way. The root receives a target from each side, so the root returns itself.

The answer is read off the final line. Node 7 is the deepest node that holds both targets below it. No deeper node qualifies.

Complexity

The brute force scans a whole subtree for each candidate node, so its worst-case time is O(n^2) for n nodes. The one-search solution visits each node at most once, so its time is O(n).

The brute force stores each collected subtree, so its extra space is O(n). The one-search solution stores only its recursion stack, one root-to-leaf path, so its space is O(h) for height h.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def subtree_values(node, values, scans):
    if node is None:
        return
    scans[0] += 1
    values.append(node.value)
    subtree_values(node.left, values, scans)
    subtree_values(node.right, values, scans)

def collect(node, depth, nodes):
    if node is None:
        return
    nodes.append((depth, node))
    collect(node.left, depth + 1, nodes)
    collect(node.right, depth + 1, nodes)

def brute_scans(root, a, b):
    nodes = []
    collect(root, 0, nodes)
    scans = [0]
    for depth, node in nodes:
        values = []
        subtree_values(node, values, scans)
    return scans[0]

def lca(node, a, b, visits):
    if node is None:
        return None
    visits[0] += 1
    if node.value == a or node.value == b:
        return node
    left = lca(node.left, a, b, visits)
    right = lca(node.right, a, b, visits)
    if left is not None and right is not None:
        return node
    if left is not None:
        return left
    return right

def make_chain(n):
    root = None
    for value in range(n, 0, -1):
        root = TreeNode(value, root)
    return root

for n in [5, 10, 20]:
    tree = make_chain(n)
    visits = [0]
    lca(tree, n - 1, n, visits)
    print("chain nodes", n, "- brute subtree scans:", brute_scans(tree, n - 1, n),
          " optimal visits:", visits[0])

The counts prove the growth claim. Doubling the chain roughly quadruples the brute force scans. The optimal visits grow only with the node count itself.

Edge cases and pitfalls

A target can be the root. The search returns the root at its first step in that case. A target can also be an ancestor of the other target, and the search returns that ancestor itself.

A missing target is the dangerous case. The search cannot tell an absent value from a found one. The last run below searches for 99, which is not in the tree, and still returns 9 with no warning.

class TreeNode:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def lca(node, a, b, visits):
    if node is None:
        return None
    visits[0] += 1
    if node.value == a or node.value == b:
        return node
    left = lca(node.left, a, b, visits)
    right = lca(node.right, a, b, visits)
    if left is not None and right is not None:
        return node
    if left is not None:
        return left
    return right

tree = TreeNode(7,
                TreeNode(3, TreeNode(9), TreeNode(2)),
                TreeNode(5, TreeNode(1), TreeNode(8)))

visits = [0]
print("root is a target:", lca(tree, 7, 8, visits).value)
visits = [0]
print("ancestor is a target:", lca(tree, 3, 2, visits).value)
visits = [0]
print("empty tree:", lca(None, 1, 2, visits))
visits = [0]
print("one target missing, 99:", lca(tree, 9, 99, visits).value)

Both targets must be present for the answer to be trusted. That condition is part of the problem statement, not a detail the code checks. Callers verify presence first, or accept the risk shown above.