vault

Lowest Common Ancestor

17 min read

Lowest Common Ancestor

Given two nodes u and v in a rooted tree, the lowest common ancestor (LCA) is the deepest node that is an ancestor of both — equivalently, the unique node on the (root → u) path that is closest to both u and v. LCA is the underlying primitive for tree-distance queries, path-aggregate queries, the tree diameter (every diameter’s midpoint is the LCA of its endpoints), competitive-programming tree problems, and many version-control internals (Git’s merge-base is exactly LCA on the commit DAG, restricted to its tree subset). Several algorithms exist with different time/space trade-offs depending on whether you have one query or many.

1. Intuition — The Family Reunion Problem

A rooted tree is a family tree: every node has exactly one parent, traceable up to the founding ancestor (root). The LCA of you and your second cousin is your shared great-grandparent — the most recent common ancestor of both branches. “Most recent” = “deepest in the tree” = “lowest” in the rooted-tree sense (rooted trees are typically drawn with root at the top, descendants below; “lowest” here means “lowest down” = “deepest” = “closest to the leaves” = the latest common ancestor as you walk from the root down).

To find it by hand: list everyone on the root-to-you path and everyone on the root-to-cousin path; the last node those two lists share is the LCA. The algorithms below are different ways of computing this efficiently — naively it would be O(n) per query, but with preprocessing we can do it in O(log n) or even O(1) per query.

2. Tiny Worked Example

Consider the tree:

                1
              /   \
             2     3
            / \     \
           4   5     6
          /     \
         7       8

Root = 1. Some LCAs:

  • LCA(7, 8) = 2 — both descend from 2 (7 via 4, 8 via 5).
  • LCA(7, 5) = 2 — 5 is a sibling of 4; 2 is the deepest shared ancestor.
  • LCA(7, 6) = 1 — different subtrees of root; only the root contains both.
  • LCA(4, 7) = 4 — when one node is an ancestor of the other, that ancestor is the LCA.
  • LCA(5, 5) = 5 — a node is its own LCA with itself.

The path from 7 to 8 in the tree is 7 → 4 → 2 → 5 → 8, length 4 edges. This length equals depth(7) + depth(8) − 2 · depth(LCA(7, 8)) = 3 + 3 − 2·1 = 4. This identity is the basis for every LCA-based tree-distance query: dist(u, v) = depth(u) + depth(v) − 2·depth(LCA(u, v)).

3. Algorithm (a) — Naive with Parent Pointers — O(h) per query

If each node stores a parent pointer, climb both u and v to the same depth, then climb both up in lockstep until they coincide.

Pseudocode:

lca_parent_pointers(u, v):
    if depth(u) > depth(v): swap(u, v)
    while depth(v) > depth(u): v := v.parent
    while u != v:
        u := u.parent
        v := v.parent
    return u

Complexity. O(h) per query where h is the tree’s height. Preprocessing is just one DFS to compute depths — O(n) time, O(n) space.

This is the simplest algorithm and what most production code implements when LCA queries are infrequent. Its weakness is that height-h walking is wasted work if the same pair of subtrees gets queried many times.

4. Algorithm (b) — Recursive Without Parent Pointers — O(n) per query

The canonical LeetCode 236 solution. No parent pointers needed; relies on a clever post-order recursion that returns either a found node or the LCA itself.

Idea. Recurse from the root. At each node, recursively search both subtrees for u and v. Three cases:

  1. The current node is u or v → return the current node (signaling “found one of them here”).
  2. Both subtree-recursions returned non-null → the current node is the split point; it is the LCA.
  3. Exactly one subtree-recursion returned non-null → propagate that result upward (it’s either an actual found node, or the LCA computed deeper).
  4. Both returned null → return null (neither u nor v is in this subtree).

Pseudocode:

lca(node, u, v):
    if node is null:           return null
    if node == u or node == v: return node
    left  := lca(node.left,  u, v)
    right := lca(node.right, u, v)
    if left != null and right != null: return node  # split point
    return left if left != null else right          # propagate up

Why it works. When the recursion returns a non-null value to a parent, it is either (a) the LCA already (and we just propagate it all the way back to the top), or (b) one of u, v (which we propagate until we meet the other, at which point the parent that sees both becomes the LCA). The post-order timing matters: we must explore both subtrees before deciding whether the current node is the LCA.

Pitfall — assumes both u and v are in the tree. If one is missing, the function returns the other (treating it as the LCA), which is wrong. Production-quality code checks presence first or augments the return to include presence flags.

Complexity. O(n) time per query (visits every node in the worst case), O(h) space (recursion stack). For a single LCA query this is asymptotically optimal — we have to be willing to look anywhere in the tree to find both nodes.

5. Algorithm (c) — Binary Lifting — O(n log n) preprocessing, O(log n) per query

The standard fast algorithm for many LCA queries on a static tree. Idea: precompute, for each node v and each k = 0, 1, ..., ⌊log₂ n⌋, the 2^k-th ancestor of v. Then to compute LCA, lift u and v to the same depth using these jumps, then lift both simultaneously by progressively smaller powers of 2 until their parents match — at which point the matching parent is the LCA.

Preprocessing. Run a DFS from the root computing depth[v] and up[v][0] = parent[v] for every node. Then fill the table:

for k from 1 to LOG:
    for each node v:
        up[v][k] = up[ up[v][k-1] ][k-1]    # 2^k jump = two 2^(k-1) jumps

O(n log n) time and space.

Query.

lca_binary_lifting(u, v):
    if depth(u) < depth(v): swap(u, v)
    diff = depth(u) - depth(v)
    # Lift u to the same depth as v.
    for k from LOG down to 0:
        if (diff >> k) & 1:
            u = up[u][k]
    if u == v: return u
    # Now lift both simultaneously, largest jump first, only when they wouldn't coincide.
    for k from LOG down to 0:
        if up[u][k] != up[v][k]:
            u = up[u][k]
            v = up[v][k]
    return up[u][0]

Why it works. Lifting u to depth depth(v) reduces the problem to “two nodes at the same depth, find their LCA.” Then for each k from large to small, if jumping both by 2^k would not yet make them coincide, do the jump (we’re not at the LCA yet); otherwise skip. After processing all k, both nodes are exactly one step below the LCA, so their parent is the LCA.

The “largest jumps first” order is critical — it’s a binary-decomposition argument: any positive integer d can be written as a sum of distinct powers of 2 (its binary representation), so any required lifting distance can be achieved by at most log d jumps. This is the same idea as binary search applied to ancestor depth.

Complexity. O(n log n) preprocessing time and space; O(log n) per query. Excellent when queries vastly outnumber preprocessing cost — i.e., many queries on a static tree.

6. Algorithm (d) — Tarjan’s Offline LCA — O((n + q) · α(n)) for q queries

Tarjan, 1979. Combines a single DFS traversal with Union-Find to answer all q queries in nearly-linear total time. Constraint: requires all queries to be known up front (offline).

Idea. During a DFS from the root, maintain a Union-Find structure keyed by node, with a separate “ancestor” attribute tracked per set. As DFS explores v’s subtree fully, union v into its parent’s set. For each query (u, w) involving v: when DFS reaches v, if the other node w has already been visited and its DFS post-order is complete, then find(w) returns the LCA of u and w.

Pseudocode (sketch):

tarjan_offline_lca(root, queries):
    # queries is a list of (u, v); answer[i] will be filled in
    color := {v: WHITE for v in tree}
    ancestor := {}                               # ancestor[find(v)] gives current candidate
    answers := [None] * len(queries)
    queries_by_node := defaultdict(list)
    for i, (u, v) in enumerate(queries):
        queries_by_node[u].append((v, i))
        queries_by_node[v].append((u, i))
    def dfs(v):
        make_set(v)
        ancestor[find(v)] = v
        for c in children(v):
            dfs(c)
            union(v, c)
            ancestor[find(v)] = v
        color[v] = BLACK
        for (other, qi) in queries_by_node[v]:
            if color[other] == BLACK:
                answers[qi] = ancestor[find(other)]
    dfs(root)
    return answers

Complexity. O((n + q) · α(n)) total, where α is the inverse Ackermann function — effectively O(n + q) for any practical input. Linear in the combined input size, asymptotically optimal up to the inverse-Ackermann factor.

The catch: it’s offline. You can’t answer one query, then think, then ask another based on the first answer — you need the full query list before starting the DFS. For online query workloads, use binary lifting (c) or Euler-tour + RMQ (e).

7. Algorithm (e) — Euler Tour + Range Minimum Query — O(n log n) preprocessing, O(1) per query

Bender & Farach-Colton, 2000 (“The LCA Problem Revisited”). The asymptotically fastest per-query algorithm: O(n) preprocessing (with the ±1-RMQ optimization) and O(1) per query. Standard sparse-table version is O(n log n) preprocessing.

Idea. Perform an Euler tour of the tree (a DFS that visits each edge twice, once going down and once coming back up). Record the depth of each node visited in the order of the tour. The LCA of u and v is then the node of minimum depth in the segment of the Euler tour between any occurrence of u and any occurrence of v. This converts LCA into a range-minimum query (RMQ) over a fixed array.

Why it works. Walking from u to v along the Euler tour traces the path u → ... → LCA(u,v) → ... → v in the tree. The shallowest (minimum-depth) node anywhere on the tour between u and v is exactly the LCA — every ancestor of both u and v is shallower than both, but the deepest such ancestor is at the path’s apex.

Preprocessing. DFS to construct the Euler tour tour[] (length 2n − 1), the depths along it depth_tour[], and first_occurrence[v] (the index in tour[] where v first appears). Then build a Sparse Table on depth_tour[] for RMQ — O(n log n) time and space.

Query.

lca_euler_rmq(u, v):
    l = first_occurrence[u]
    r = first_occurrence[v]
    if l > r: swap(l, r)
    idx = sparse_table_argmin(l, r)              # O(1) with sparse table
    return tour[idx]

Complexity. Sparse-table version: O(n log n) preprocessing, O(1) per query. The Bender–Farach-Colton optimization (exploiting the fact that consecutive depth_tour entries differ by exactly ±1) gives O(n) preprocessing with O(1) queries — theoretically optimal but rarely implemented because the constant factor and code complexity outweigh the asymptotic gain in practice.

8. The BST Special Case — O(h) per query, no preprocessing

In a Binary Search Tree, LCA is trivial: descend from the root, and the LCA is the first node v such that min(u, w) ≤ v ≤ max(u, w) — i.e., the values u and w straddle v (one ≤ v, the other ≥ v) or one of them equals v. While the current node’s value is greater than both u and w, go left; while less than both, go right; otherwise the current node is the LCA.

def lca_bst(root, u, w):
    if u.val > w.val: u, w = w, u   # ensure u.val <= w.val
    while root:
        if root.val > w.val:
            root = root.left
        elif root.val < u.val:
            root = root.right
        else:
            return root             # u.val <= root.val <= w.val

O(h) time, O(1) space (iterative). LC 235.

This is much faster than the general algorithm because the BST invariant lets us prune one subtree per step instead of exploring both. Always check whether the input is a BST before reaching for the general algorithm.

9. Python Implementation — The Two Most-Used

The recursive without-parent-pointers algorithm (LC 236):

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
 
def lca(root, u, v):
    """LC 236. Assumes both u and v are present in the tree."""
    if root is None or root is u or root is v:
        return root
    left  = lca(root.left,  u, v)
    right = lca(root.right, u, v)
    if left and right:
        return root
    return left if left else right

Binary lifting on a general tree given as parent array and adjacency:

import math
 
class LCABinaryLifting:
    def __init__(self, n, adj, root=0):
        self.n = n
        self.LOG = max(1, math.ceil(math.log2(n)))
        self.depth = [0] * n
        self.up = [[-1] * self.LOG for _ in range(n)]
        # DFS to set parent and depth.
        from collections import deque
        order, parent = [], [-1] * n
        stack = [root]
        seen = [False] * n; seen[root] = True
        while stack:
            v = stack.pop()
            order.append(v)
            for w in adj[v]:
                if not seen[w]:
                    seen[w] = True
                    parent[w] = v
                    self.depth[w] = self.depth[v] + 1
                    stack.append(w)
        for v in order:
            self.up[v][0] = parent[v]
        for k in range(1, self.LOG):
            for v in range(n):
                p = self.up[v][k-1]
                self.up[v][k] = self.up[p][k-1] if p != -1 else -1
 
    def query(self, u, v):
        if self.depth[u] < self.depth[v]:
            u, v = v, u
        diff = self.depth[u] - self.depth[v]
        for k in range(self.LOG):
            if (diff >> k) & 1:
                u = self.up[u][k]
        if u == v:
            return u
        for k in range(self.LOG - 1, -1, -1):
            if self.up[u][k] != self.up[v][k]:
                u = self.up[u][k]
                v = self.up[v][k]
        return self.up[u][0]

10. Complexity Summary

AlgorithmPreprocessingPer-QuerySpaceWhen to use
(a) Parent pointers, climbO(n) (compute depths)O(h)O(n)Few queries, simple code
(b) Recursive (no parent ptrs)O(0)O(n)O(h)Single query on a small tree (LC 236 default)
(c) Binary liftingO(n log n)O(log n)O(n log n)Many online queries on a static tree
(d) Tarjan offline + Union-FindO(n + q · α(n)) totalamortized O(α(n))O(n + q)All queries known up front
(e) Euler tour + Sparse Table RMQO(n log n)O(1)O(n log n)Massive online query loads, can spend memory
(e′) Bender–Farach-Colton ±1 RMQO(n)O(1)O(n)Theoretically optimal; rare in practice
BST-only LCAO(0)O(h)O(1)Tree is a BST

Recommendation by use case:

  • Single LCA query in an interview context → algorithm (b). Cleanest code, no preprocessing, O(n) is fine for one query.
  • Many queries on a static tree → algorithm (c) binary lifting. Great preprocessing/query trade-off; reasonable code complexity.
  • All queries known offline → algorithm (d) Tarjan. Optimal asymptotic total runtime.
  • Online queries with O(1) per-query needs → algorithm (e) Euler + RMQ.
  • BST input → BST-specific descent. Always.

11. Pitfalls

11.1 Assuming Both Targets Are in the Tree

Algorithm (b) returns a non-null value as soon as it sees one of u or v — even if the other is not actually in the tree. The function then returns the found node, which the caller misinterprets as “LCA.” LC 236’s problem statement guarantees both nodes are present, sidestepping this; LC 1644 (“LCA II”) removes that guarantee and requires explicit presence checks. Always read the problem statement for this assumption.

11.2 LCA of a Node and Itself

By convention LCA(v, v) = v. Algorithm (b) handles this naturally because node == u short-circuits at depth depth(v). Edge-case to mentally verify: when u is an ancestor of v (e.g., u = root), LCA(u, v) = u. Algorithm (b) handles this too — when the recursion finds u it returns u immediately, which propagates all the way up.

11.3 Confusing “Lowest” with “Highest”

In rooted trees drawn root-at-top, “lowest” = deepest = closest to leaves. The LCA is the deepest common ancestor. Some students confuse this with “the highest common ancestor” (which is always the root if both nodes are in the tree, and trivially uninteresting).

11.4 Binary Lifting Off-By-One

The “lift u by diff to match v’s depth” loop and the “lift both by largest power of 2 first” loop must use consistent semantics. A common bug: for k from 0 to LOG (ascending) instead of for k from LOG down to 0. The descending order is required for the second loop’s correctness — we need to commit to large jumps only when they wouldn’t overshoot. Trace through on a small example before trusting the implementation.

11.5 Tarjan Forgetting the Color/Visited Check

The query is only answerable when the other endpoint of the query has already been fully processed (color = BLACK). Querying before that returns garbage. The if color[other] == BLACK check inside the post-DFS loop is critical.

11.6 Euler Tour Length

The Euler tour has length 2n − 1 (each of the n − 1 edges contributes 2 visits, plus the starting node). Allocating arrays of size n instead of 2n − 1 is a classic off-by-one.

11.7 LCA on a DAG

Strictly, LCA is defined on rooted trees. The generalization to directed acyclic graphs (“LCA on a DAG”) is more subtle: a DAG can have multiple LCAs (no unique “deepest” common ancestor) or none. Git’s git merge-base uses a DAG variant — when it returns multiple results, you have a “criss-cross merge” requiring recursive merging. None of the algorithms above handle this directly; specialized DAG algorithms exist.

12. Diagram — LCA Recursion Splitting at the Right Node

flowchart TD
    R((1)) --> A((2))
    R --> B((3))
    A --> C((4))
    A --> D((5))
    C --> E((7))
    D --> F((8))
    B --> G((6))

What this diagram shows. The tree from §2. Suppose we query LCA(7, 8) using algorithm (b). The recursion descends from root 1; recursing left into 2, then both into 4 (eventually returns 7 because that subtree contains node 7) and into 5 (eventually returns 8). Back at node 2, the left recursion returned 7 (non-null) and the right recursion returned 8 (non-null) — both subtrees contributed, so node 2 is the split point and is returned as the LCA. The return value 2 then propagates up through node 1: at node 1, the left recursion returned 2 (non-null, the LCA) and the right recursion returned null (subtree 3 contains neither 7 nor 8), so we propagate 2 up. Final answer: LCA(7, 8) = 2. The “split point” intuition — where the two upward paths from u and v first merge — is the unifying mental model behind every LCA algorithm.

13. Common Interview Problems

LC #ProblemBest algorithm
236LCA of a Binary TreeAlgorithm (b) — recursive
235LCA of a Binary Search TreeBST-specific descent
1644LCA of a Binary Tree II (nodes may not exist)(b) augmented with presence flags
1650LCA of a Binary Tree III (parent pointers given)Algorithm (a) or “two pointers like cycle-finding” trick
1676LCA of a Binary Tree IV (k nodes)Generalize (b) to a list of targets
865Smallest Subtree with all the Deepest NodesModified post-order returning (depth, LCA-candidate)
1740Find Distance in a Binary TreeLCA + depth difference (§2 identity)

LC 1650 is worth a special note: with parent pointers, you can use a Floyd-style two-pointer trick — start two pointers from u and v, walk each one upward, and when one hits the root, redirect it to the other node’s start. They’re guaranteed to meet at the LCA. This is the same arithmetic as cycle-detection’s “fast/slow meet” reasoning.

14. Open Questions

  • The O(n) Bender–Farach-Colton algorithm is asymptotically optimal but rarely used. Is there a simpler O(n)/O(1) LCA algorithm with reasonable constants?
  • In dynamic-tree settings (link-cut trees, Euler-tour trees), LCA queries become O(log n) amortized. How do these compare to binary lifting in real workloads?
  • DAG-LCA (Git’s merge-base) is genuinely harder. The 2008 paper “Algorithms for Computing the Lowest Common Ancestors in a Directed Acyclic Graph” (Czumaj, Kowaluk & Lingas) gives subquadratic results; few implementations use them.

15. See Also

Graph View

Backlinks