Problem 27 · Trees

Lowest Common Ancestor of a Binary Tree

MediumClassic DSA & systems

01Problem

Given a binary tree and two nodes p and q in it, return their lowest common ancestor.

02Key insight

Post-order: a subtree returns p or q if it contains one; the first node where both left and right return non-null is the LCA. In a BST you can instead walk down by value.

03Solution

solution.pypython18 lines

from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional

@dataclass(eq=False)
class TreeNode:
    val: int
    left: Optional[TreeNode] = field(default=None, repr=False)
    right: Optional[TreeNode] = field(default=None, repr=False)

def lowest_common_ancestor(root: Optional[TreeNode], p: TreeNode, q: TreeNode) -> Optional[TreeNode]:
    if root is None or root is p or root is q:
        return root
    left = lowest_common_ancestor(root.left, p, q)
    right = lowest_common_ancestor(root.right, p, q)
    if left and right:
        return root
    return left or right

Try it first.

TimeO(n)

SpaceO(h)

tests.py · 3 passing

tests.pypython9 lines

T = TreeNode
n7, n4 = T(7), T(4)
n2 = T(2, n7, n4)
n5 = T(5, T(6), n2)
n1 = T(1, T(0), T(8))
root = T(3, n5, n1)
assert lowest_common_ancestor(root, n5, n1) is root
assert lowest_common_ancestor(root, n5, n4) is n5
assert lowest_common_ancestor(root, n7, n4) is n2

04Staff-level follow-up

Many LCA queries on a static tree? Precompute binary lifting (O(n log n)) for O(log n) per query, or Euler tour + sparse-table RMQ for O(1) queries.