Lowest Common Ancestor (LCA), in depth: naive climbing, binary lifting, Euler tour with sparse tables, Tarjan's offline algorithm, and how to choose

The example tree and the vocabulary

The examples use the ten-node tree below, rooted at 0. Every algorithm needs a root, a parent for every node and a depth, with the root at depth 0, all from one traversal. Inputs usually arrive as an undirected edge list, so the traversal also fixes the orientation, and a different root changes every answer.

Method 0: climb with depths

The naive method equalises depth and then walks both nodes up in lockstep until they meet. It needs only parent and depth, costs O(n) to prepare and O(h) per query, where h is the tree height.

def lca_naive(u, v, parent, depth):
    # parent[root] == root; depth[root] == 0
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]
    while u != v:
        u, v = parent[u], parent[v]
    return u

On a balanced tree h is about log n. On a path-shaped tree h is n and each query is linear. Keep it anyway as the reference that every faster method is tested against.

Method 1: binary lifting

Binary lifting stores, for every node, its ancestors at distances 1, 2, 4, 8 and so on: up[k][v] is the 2^k-th ancestor of v. The table is filled level by level with one identity: jumping 2^k equals two jumps of 2^(k-1). Setting the root's ancestor to itself makes jumps past the root saturate harmlessly.

A query first lifts the deeper node by the depth difference, read in binary. If the nodes are now equal, one was the other's ancestor. Otherwise try jumps from largest to smallest, taking one only when it lands the nodes on different ancestors. Both then sit just below the LCA, so the answer is their parent.

def build_lifting(n, root, adj):
    LOG = max(1, (n - 1).bit_length())      # 2**LOG > any depth (depth <= n - 1)
    up = [[root] * n for _ in range(LOG)]    # root is its own parent
    depth = [0] * n
    seen = [False] * n
    seen[root] = True
    order = [root]
    for u in order:                          # iterative BFS
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                up[0][v] = u
                depth[v] = depth[u] + 1
                order.append(v)
    for k in range(1, LOG):
        prev, cur = up[k - 1], up[k]
        for v in range(n):
            cur[v] = prev[prev[v]]
    return up, depth, LOG


def lca_lift(u, v, up, depth, LOG):
    if depth[u] < depth[v]:
        u, v = v, u
    diff, k = depth[u] - depth[v], 0
    while diff:                              # lift u by diff
        if diff & 1:
            u = up[k][u]
        diff >>= 1
        k += 1
    if u == v:
        return u
    for k in range(LOG - 1, -1, -1):
        if up[k][u] != up[k][v]:
            u, v = up[k][u], up[k][v]
    return up[0][u]

Trace LCA(7, 9). Both are at depth 3 and LOG is 4. For k = 3 and k = 2 both jumps land on the root, so they are skipped. For k = 1, 7 jumps to 1 and 9 jumps to 2; they differ, so both move. For k = 0, both parents are 0, equal, skipped. The answer is the parent of 1, which is 0. For LCA(8, 3), 8 is lifted by one to 4, then no jump separates 4 and 3, and the answer is their shared parent 1.

Binary lifting costs O(n log n) time and memory to build and O(log n) per query. It answers queries online, gives k-th ancestor queries from the same table, and a new leaf can be appended in O(log n) by filling its own column. The table can also carry path aggregates, such as the maximum edge weight over each jump.

Method 2: Euler tour plus range minimum

The second method turns LCA into a range minimum query. Walk the tree depth-first and write down a node every time the walk visits it, including each return from a child. That sequence, the Euler tour, has exactly 2n - 1 entries. Record first[v], the first position of each node.

Between the first visits of u and v, the walk passes through their LCA and never climbs above it. So the LCA is the node with the smallest depth in the tour between first[u] and first[v]. The minimum is over depth, not over node id; confusing the two is the classic bug.

A sparse table answers range minimum in O(1): sparse[j][i] holds the position of the minimum depth in the block of length 2^j starting at i, and any range is covered by two overlapping blocks.

def build_euler_rmq(n, root, adj):
    euler, first = [], [-1] * n
    depth, parent, it = [0] * n, [-1] * n, [0] * n
    stack = [root]
    first[root] = 0
    euler.append(root)
    while stack:                             # iterative DFS
        u = stack[-1]
        if it[u] < len(adj[u]):
            v = adj[u][it[u]]
            it[u] += 1
            if v == parent[u]:
                continue
            parent[v], depth[v] = u, depth[u] + 1
            first[v] = len(euler)
            euler.append(v)
            stack.append(v)
        else:
            stack.pop()
            if stack:
                euler.append(stack[-1])
    m = len(euler)                           # 2n - 1
    better = lambda a, b: a if depth[euler[a]] <= depth[euler[b]] else b
    sparse = [list(range(m))]                # argmin over blocks of 2**j
    j = 1
    while (1 << j) <= m:
        prev, half = sparse[-1], 1 << (j - 1)
        sparse.append([better(prev[i], prev[i + half]) for i in range(m - (1 << j) + 1)])
        j += 1
    return euler, first, depth, sparse


def lca_euler(u, v, euler, first, depth, sparse):
    l, r = sorted((first[u], first[v]))
    j = (r - l + 1).bit_length() - 1
    a, b = sparse[j][l], sparse[j][r - (1 << j) + 1]
    return euler[a] if depth[euler[a]] <= depth[euler[b]] else euler[b]

In the example, first[7] = 5 and first[9] = 15. The eleven entries from 5 to 15 are 7 4 8 4 1 0 2 5 2 6 9, and the shallowest is 0 at position 10. For LCA(7, 3) the range from first[3] = 2 to 5 is 3 1 4 7, whose shallowest entry is 1.

Building costs O(n log n) and queries cost O(1) with two table reads. A segment tree over the tour instead gives O(n) memory and O(log n) queries, which is sometimes the better trade. The Farach-Colton and Bender refinement reaches O(n) preprocessing with O(1) queries, but is rarely worth its constant factors.

Method 3: Tarjan's offline algorithm

If every query is known up front, one DFS answers all of them using union-find. When a subtree finishes, it is merged into its parent's set, whose recorded ancestor is that parent. When u finishes, any finished node w sits in a set whose ancestor is the deepest node still on the stack above w: exactly LCA(u, w).

def lca_offline(n, root, adj, queries):
    dsu, anc, done = list(range(n)), list(range(n)), [False] * n
    pending = [[] for _ in range(n)]
    for i, (a, b) in enumerate(queries):
        pending[a].append((b, i))
        pending[b].append((a, i))
    ans = [-1] * len(queries)

    def find(x):
        while dsu[x] != x:
            dsu[x] = dsu[dsu[x]]             # path halving
            x = dsu[x]
        return x

    parent, it, stack = [-1] * n, [0] * n, [root]
    while stack:
        u = stack[-1]
        if it[u] < len(adj[u]):
            v = adj[u][it[u]]
            it[u] += 1
            if v != parent[u]:
                parent[v] = u
                stack.append(v)
            continue
        stack.pop()                          # subtree of u finished
        done[u] = True
        for w, i in pending[u]:
            if done[w]:
                ans[i] = anc[find(w)]
        if stack:                            # merge into parent
            p = stack[-1]
            ru, rp = find(u), find(p)
            dsu[ru] = rp
            anc[rp] = p
    return ans

Trace the example with children visited in id order. Node 3 finishes first and is merged into 1's set, whose ancestor is 1. When 7 finishes, 3 is already done, so LCA(7, 3) is the ancestor of 3's set: 1. Node 9 is not done yet, so that query waits. When 9 finishes, 7's set has been merged through 4 and 1 into 0's set, because 1's subtree is complete and 0 is still on the stack, so LCA(7, 9) is 0.

Tarjan's algorithm costs O((n + q) alpha(n)) with a full union-find, and O(n + q) memory. That is the least memory of the fast methods, but it cannot answer a query that arrives later. For the union-find details, see Union-Find in depth.

Choosing an algorithm

Memory decides more choices than asymptotic query time. With n = 10^6, binary lifting holds 20 levels of a million entries: 80 MB as 32-bit ints, far more as Python lists, so use primitive arrays. The Euler sparse table is larger still. For traversal and orientation, see BFS and DFS in depth; for range structures, segment trees and Fenwick trees.

Worked example: nearest shared category in a product taxonomy

A retailer's taxonomy has 400,000 categories, and a recommendation service asks which category two viewed products share most specifically, 50,000 times a second. The tree changes daily. Queries are online and latency-sensitive, so the team rebuilds an Euler tour plus sparse table in 32-bit arrays at each load and swaps it in atomically. A query is two array reads.

Distance also falls out: the service uses depth[a] + depth[b] - 2 * depth[l] as a similarity penalty. A nightly job over 200 million co-purchase pairs uses Tarjan's algorithm instead, because every pair is known up front and memory is tight.

One caution: git merge-base is not tree LCA. Commit history is a DAG, and two commits can have several merge bases.

Failure modes

Testing it

LCA code is easy to get almost right. Test every fast method against the naive climb on many small random trees.

import random

def random_tree(n):
    adj = [[] for _ in range(n)]
    for v in range(1, n):
        u = random.randrange(v)
        adj[u].append(v); adj[v].append(u)
    return adj

for trial in range(500):
    n = random.randint(1, 60)
    adj = random_tree(n)
    up, depth, LOG = build_lifting(n, 0, adj)
    e = build_euler_rmq(n, 0, adj)
    qs = [(random.randrange(n), random.randrange(n)) for _ in range(40)]
    off = lca_offline(n, 0, adj, qs)
    for (a, b), o in zip(qs, off):
        ref = lca_naive(a, b, up[0], depth)
        assert ref == lca_lift(a, b, up, depth, LOG) == lca_euler(a, b, *e) == o

Random trees are shallow, so also test a path of 100,000 nodes: that finds recursive traversals and undersized LOG values.

What to do next

1. Write the naive climb first and keep it as the oracle in your tests.
2. Decide between online and offline: if all queries are known up front, start with Tarjan's algorithm.
3. For online queries on a static tree, use binary lifting when you also need k-th ancestors or path maximums, and Euler tour plus sparse table when query latency dominates.
4. Estimate memory at your real node count before choosing an O(n log n) table, and use primitive arrays.
5. Make every traversal iterative and test on a path-shaped tree of at least 100,000 nodes.
6. Run the randomized cross-check above in CI whenever the tree code changes.