8.7 Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor of both.

algorithmstreesdata-structures

8.7 Lowest Common Ancestor

The Lowest Common Ancestor (LCA) of two nodes is the deepest node that is an ancestor of both. It is one of the most important tree queries because many other problems reduce to it. Distance queries, path queries, hierarchy analysis, version-control ancestry, organizational charts, file systems, and network routing all rely on the same underlying operation.

Consider the following tree:

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

The lowest common ancestor of nodes 7 and 8 is:

4

The lowest common ancestor of nodes 3 and 8 is:

1

The word "lowest" is important. Every common ancestor qualifies, but we want the deepest one.

This recipe develops several approaches, beginning with a simple solution and then introducing the binary lifting technique used in high-performance systems.

Problem

You need to find the nearest shared ancestor of two nodes in a rooted tree.

Solution

The simplest solution stores parent pointers and walks upward.

Suppose:

parent := []int{
    -1, // 0
     0, // 1
     0, // 2
     1, // 3
     1, // 4
     2, // 5
     2, // 6
     4, // 7
     4, // 8
}

First compute depths:

func computeDepth(
    tree [][]int,
    node int,
    currentDepth int,
    depth []int,
) {
    depth[node] = currentDepth

    for _, child := range tree[node] {
        computeDepth(
            tree,
            child,
            currentDepth+1,
            depth,
        )
    }
}

Then equalize depths.

for depth[u] > depth[v] {
    u = parent[u]
}

for depth[v] > depth[u] {
    v = parent[v]
}

Finally move both nodes upward together.

for u != v {
    u = parent[u]
    v = parent[v]
}

The meeting point is the LCA.

Complete implementation:

func lca(
    u int,
    v int,
    parent []int,
    depth []int,
) int {
    for depth[u] > depth[v] {
        u = parent[u]
    }

    for depth[v] > depth[u] {
        v = parent[v]
    }

    for u != v {
        u = parent[u]
        v = parent[v]
    }

    return u
}

This approach is simple and surprisingly effective for small trees.

Discussion

The core idea is that ancestors form a chain.

For node 8:

8 → 4 → 1 → 0

For node 3:

3 → 1 → 0

The first shared node is:

1

That node is the answer.

The naive algorithm explicitly walks those chains.

While straightforward, it may require traversing large portions of the tree for every query.

If the tree contains millions of nodes and millions of queries, we need something faster.

Why Depth Matters

Suppose:

depth(7) = 3
depth(2) = 1

These nodes cannot be compared directly because they are at different levels.

The first step is always:

Move the deeper node upward.

For example:

7 → 4 → 1

Now both nodes are at depth 1.

Only then can they move upward together.

This equalization step appears in nearly every LCA algorithm.

Binary Lifting

The standard optimization is Binary Lifting.

Instead of storing only:

parent[node]

store ancestors at powers of two:

2^0 ancestor
2^1 ancestor
2^2 ancestor
2^3 ancestor
...

For example:

Power Meaning
0 Parent
1 Grandparent
2 4th ancestor
3 8th ancestor
4 16th ancestor

This allows large jumps upward.

Instead of:

8 → 4 → 1 → 0

we may jump directly:

8 → 0

using a power-of-two ancestor.

Building the Ancestor Table

Let:

up[node][k]

represent the 2^k ancestor.

The first column contains direct parents.

for node := 0; node < n; node++ {
    up[node][0] = parent[node]
}

Higher powers are built recursively.

for k := 1; k < LOG; k++ {
    for node := 0; node < n; node++ {
        ancestor := up[node][k-1]

        if ancestor != -1 {
            up[node][k] = up[ancestor][k-1]
        } else {
            up[node][k] = -1
        }
    }
}

This preprocessing takes:

O(n log n)

time.

Lifting a Node

Suppose we want to move upward by 13 levels.

Binary representation:

13 = 8 + 4 + 1

Therefore:

2^3 jump
2^2 jump
2^0 jump

Implementation:

func lift(
    node int,
    distance int,
    up [][]int,
) int {
    bit := 0

    for distance > 0 {
        if distance&1 == 1 {
            node = up[node][bit]
        }

        distance >>= 1
        bit++
    }

    return node
}

Instead of taking 13 parent steps, we perform only a few jumps.

Binary Lifting LCA Query

The complete strategy:

  1. Equalize depths.
  2. Lift both nodes upward until their ancestors differ.
  3. Return the parent of either node.
func lca(
    u int,
    v int,
    depth []int,
    up [][]int,
) int {
    if depth[u] < depth[v] {
        u, v = v, u
    }

    u = lift(
        u,
        depth[u]-depth[v],
        up,
    )

    if u == v {
        return u
    }

    for k := len(up[0]) - 1; k >= 0; k-- {
        if up[u][k] != up[v][k] {
            u = up[u][k]
            v = up[v][k]
        }
    }

    return up[u][0]
}

Query complexity becomes:

O(log n)

instead of:

O(n)

in the worst case.

Distance Using LCA

One reason LCA is useful is that it immediately enables distance queries.

Consider:

u
 \\n  \\n  LCA
  /
 /
v

Distance can be computed using depths:

depth(u)
+
depth(v)
-
2 × depth(LCA)

For example:

depth(7) = 3
depth(3) = 2
depth(LCA) = 1

Distance:

3 + 2 - 2×1 = 3

The path length is three edges.

This formula appears throughout tree algorithms.

LCA via Euler Tour

Another popular approach transforms the tree into an array.

A DFS produces an Euler Tour:

0 1 3 1 4 7 4 8 4 1 0 ...

The LCA problem becomes a range minimum query over depths.

This approach is often used when:

  • Query count is extremely large.
  • A range-minimum structure already exists.
  • Offline processing is acceptable.

The binary lifting method is generally easier to implement and is the approach most commonly used in practice.

Applications

LCA appears in many domains.

File Systems

/home/projects/app
/home/projects/docs

Common ancestor:

/home/projects

Organizational Charts

Developer A
Developer B

Common manager:

Engineering Manager

Version Control

Commit A
Commit B

Common ancestor:

Merge base

Network Routing

Two endpoints may share a common routing subtree.

LCA identifies that shared branch.

Tree Dynamic Programming

Many path-based algorithms reduce to LCA plus additional preprocessing.

Complexity Analysis

Parent-Walking Method

Operation Complexity
Preprocessing O(n)
Query O(n)
Memory O(n)

Binary Lifting

Operation Complexity
Preprocessing O(n log n)
Query O(log n)
Memory O(n log n)

Euler Tour + RMQ

Operation Complexity
Preprocessing O(n log n)
Query O(1) or O(log n)
Memory O(n log n)

The best choice depends on the ratio of preprocessing cost to query volume.

Common Mistakes

A frequent mistake is forgetting to equalize depths before moving both nodes upward.

Consider:

u depth = 10
v depth = 3

If both move upward together immediately, the deeper node may skip over the correct answer.

Another mistake is confusing:

Lowest

with:

First found

The first common ancestor encountered during traversal is not necessarily the deepest one.

A third mistake occurs during binary lifting table construction.

This line:

up[node][k] = up[ancestor][k-1]

depends on the previous level already being computed correctly. Incorrect initialization propagates errors throughout the table.

Takeaway

Lowest Common Ancestor is one of the foundational tree queries. The naive parent-walking approach is easy to understand and useful for small trees. Binary Lifting extends the same idea with power-of-two jumps, reducing query time from linear to logarithmic. Once LCA is available, many higher-level operations become simple formulas, including distance queries, path analysis, hierarchy processing, and numerous tree dynamic programming techniques.