Algorithm Deep Dive: Lowest Common Ancestor (LCA)

The Problem Behind LCA

A rooted tree turns “above” and “below” into precise relationships. A vertex $a$ is an ancestor of $v$ when $a$ lies on the unique path from the root to $v$. For two vertices $u$ and $v$, their lowest common ancestor is the common ancestor with greatest depth.

A single query is easy: repeatedly climb parents until the two paths meet. The interesting algorithmic problem is answering thousands or millions of queries on the same static tree. Preprocessing converts repeated climbing into fast jumps or range minima.

LCA is a preprocessing trade-off

No tableStore one parent per vertex and spend up to $O(N)$ time climbing for every query.

Jump tableStore power-of-two ancestors and answer a query in $O(\log N)$ time.

Euler + RMQFlatten the traversal, preprocess range minima, and reduce each LCA query to an array query.

Ancestor Intuition: Where Two Root Paths Merge

Because a tree has exactly one simple path between any pair of vertices, the paths $u\leadsto root$ and $v\leadsto root$ eventually merge and never split again. The first shared vertex while walking upward is therefore the deepest shared ancestor.

The root is part of both ancestor sets, but it is not the answer when a deeper shared ancestor exists. Also note that a vertex counts as its own ancestor, so $LCA(u,u)=u$.

The root is part of the input

The same undirected tree can produce different ancestor relationships under a different root. LCA is defined on a rooted tree, not merely an undirected tree.

Ancestor cases are ordinary cases

If $u$ lies on the root path of $v$, then $LCA(u,v)=u$. A correct algorithm should detect this naturally after equalizing depths.

Working Principle: Binary Lifting

Binary lifting stores exponentially long parent jumps. Define up[v][j] as the ancestor $2^j$ edges above $v$. The first column is the ordinary parent; every later column doubles the jump:

$$up[v][0]=parent[v], \qquad up[v][j]=up\big[up[v][j-1]\big][j-1].$$

For example, the eighth ancestor is the fourth ancestor of the fourth ancestor. Only $lceil\log_2 N\rceil$ columns are needed because no simple root path contains more than $N-1$ edges.

Powers of two are a compact vocabulary for every possible climb. The depth gap 2 uses one $2^1$ jump; a gap such as 13 would use jumps $8+4+1$.

Preprocess parents and depths.Root the tree, record depth[v], and fill the direct-parent column up[v][0].

Build doubling columns.Use the recurrence to fill the second, fourth, eighth, and higher ancestors for every vertex.

Equalize query depths.Lift the deeper vertex by the set bits of the depth difference. If the vertices become equal, that vertex is the answer.

Lift together without crossing the answer.Scan jump sizes from largest to smallest. When the two proposed ancestors differ, accept both jumps.

Return one parent.After the scan, the two vertices are distinct children immediately below their LCA, so return up[u][0].

Why scan simultaneous jumps from large to small?

The query is looking for the highest safe climb that keeps the two ancestors different. A large-to-small greedy scan builds the maximum total climb that stays strictly below the LCA. Scanning upward from small jumps would move too cautiously and lose the logarithmic guarantee.

Euler Tour + Range Minimum Query

A second viewpoint replaces ancestor jumps with an array problem. Perform a depth-first traversal and append a vertex when entering it and again whenever the traversal returns to it from a child. For a tree with $N$ vertices, this Euler sequence has $2N-1$ entries.

Between the first visits to $u$ and $v$, DFS must climb to their LCA before it can enter the other branch. It never climbs above that ancestor inside the interval, so the minimum-depth entry identifies the LCA.

Create the Euler and depth arrays.Record every entry and return during DFS, plus the first index at which each vertex appears.

Map the query to an interval.Let $L=first[u]$ and $R=first[v]$; swap them when $L>R$.

Ask for a minimum-depth index.An RMQ structure returns the position with minimum depth in depthEuler[L..R].

Translate back to a vertex.The Euler entry stored at that minimum position is $LCA(u,v)$.

Sparse table versus linear-space ±1 RMQ

A sparse table is the simplest static choice: $O(N\log N)$ preprocessing and space, then $O(1)$ RMQ queries. The Euler depth array has extra structure—adjacent values differ by exactly 1—which specialized ±1 RMQ methods exploit to reach $O(N)$ preprocessing and space with $O(1)$ queries.

The Euler reduction itself does not automatically imply linear preprocessing; that depends on the RMQ structure chosen.

Worked Binary-Lifting Trace

Use the second figure and query $LCA(13,9)$. Vertex 13 has depth 5, vertex 9 has depth 3, and the gap is 2.

Phase	Test	Accepted move	State afterward
Equalize	$5-3=2=2^1$	`13 → up[13][1] = 8`	`u=8, v=9`, both depth 3
Ancestor check	`8 != 9`	Continue	Both remain below the answer
Large jumps	Higher ancestors are equal	Reject those jumps	Jumping would reach or cross the LCA
Final parent	`up[8][0] = up[9][0] = 5`	Return 5	`LCA(13,9)=5`

Intuition: two hikers are on different trails leading to the same summit. First move the lower hiker up to the same altitude. Then let both take the largest safe shortcuts that keep them on different trails. When no such shortcut remains, the next shared checkpoint is the LCA.

Why the Algorithms Are Correct

Binary lifting

1. Equalization preserves the answer

Only the deeper vertex moves, and it moves along its unique root path. No common ancestor can lie below the shallower vertex's depth, so these jumps cannot skip the LCA.

2. Accepted paired jumps stay below it

If up[u][j] and up[v][j] differ, both are still in different branches beneath the LCA. Moving to them is safe.

3. Rejected jumps fence in the answer

If the proposed ancestors are equal, that jump reaches the same ancestor and may reach or pass the LCA. Rejecting it keeps both vertices strictly below the answer.

4. One final edge reaches it

After all powers are tested, no positive jump can keep the vertices apart. Their direct parents must therefore be the same vertex: the LCA.

Euler tour plus RMQ

Assume first[u] ≤ first[v]. After DFS first visits $u$, it must climb to $LCA(u,v)$ before it can enter the branch containing $v$. During this interval it cannot climb above the LCA—doing so would leave the smallest subtree containing both vertices. Therefore the minimum depth in the interval is exactly the depth of their LCA, and the Euler vertex at a minimum position is the correct answer.

Useful Query Recipes Built on LCA

Unweighted distance

When depth counts edges, $$dist(u,v)=depth[u]$$
$$+depth[v]-2,depth[LCA(u,v)].$$

Weighted distance

Store $rootDist[x]$, the sum of edge weights from the root: $$dist(u,v)=rootDist[u]+rootDist[v]$$
$$-2\,rootDist[LCA(u,v)].$$

K-th ancestor

Decompose $k$ into binary and apply up[v][j] for every set bit. This is the same depth-equalization operation used inside LCA.

Does x lie on path u-v?

Check whether $dist(u,x)+dist(x,v)=dist(u,v)$. With LCA-based distances, each term is available in logarithmic or constant query time.

Depth is not weighted distance

depth[v] normally counts edges and is used to align vertices. In a weighted tree, the distance formula must use a separate root-distance sum. Substituting depth is correct only when every edge weight is 1.

Complexity and Method Selection

Method	Preprocessing	Per query	Space	Best fit
Parent climbing	$O(N)$	$O(N)$ worst case	$O(N)$	A few queries or tiny trees
Binary lifting	$O(N\log N)$	$O(\log N)$	$O(N\log N)$	Default practical choice; also supports k-th ancestors
Euler tour + sparse table	$O(N\log N)$	$O(1)$	$O(N\log N)$	Very many static LCA queries
Euler tour + ±1 RMQ	$O(N)$	$O(1)$	$O(N)$	Optimal asymptotics with more implementation complexity
Tarjan offline LCA	$O((N+Q)\alpha(N))$ total	Offline batch only	$O(N+Q)$	All queries known before processing

The shortest mental model: binary lifting searches vertically with power-of-two jumps; Euler plus RMQ searches horizontally inside a traversal array.

Both work because a rooted tree gives every vertex one unique path to the root.

Implementation

The implementation below uses binary lifting because it is compact, versatile, and usually the best default. Preprocessing is iterative so a path-shaped tree does not overflow the language call stack. It also validates that the input is one connected acyclic tree.

class BinaryLiftingLCA:
    def __init__(self, adj, root=0):
        self.n = len(adj)
        if self.n == 0 or not 0 <= root < self.n:
            raise ValueError("need a non-empty tree and a valid root")

        self.root = root
        self.log = max(1, self.n.bit_length())
        self.depth = [0] * self.n
        parent = [-1] * self.n
        parent[root] = root
        order = [root]

        # Iterative traversal: parent doubles as the visited marker.
        for u in order:
            for v in adj[u]:
                if not 0 <= v < self.n:
                    raise ValueError("neighbor index out of range")
                if v == u:
                    raise ValueError("input contains a self-loop")
                if v == parent[u]:
                    continue
                if parent[v] != -1:
                    raise ValueError("input contains a cycle")
                parent[v] = u
                self.depth[v] = self.depth[u] + 1
                order.append(v)

        if len(order) != self.n:
            raise ValueError("input tree is disconnected")

        self.up = [[root] * self.log for _ in range(self.n)]
        for v in range(self.n):
            self.up[v][0] = parent[v]
        for j in range(1, self.log):
            for v in range(self.n):
                self.up[v][j] = self.up[self.up[v][j - 1]][j - 1]

    def _check_vertex(self, v):
        if not 0 <= v < self.n:
            raise IndexError("vertex out of range")

    def kth_ancestor(self, v, k):
        self._check_vertex(v)
        if k < 0 or k > self.depth[v]:
            raise ValueError("k must be between 0 and depth[v]")
        for j in range(self.log):
            if (k >> j) & 1:
                v = self.up[v][j]
        return v

    def lca(self, u, v):
        self._check_vertex(u)
        self._check_vertex(v)
        if self.depth[u] < self.depth[v]:
            u, v = v, u

        u = self.kth_ancestor(u, self.depth[u] - self.depth[v])
        if u == v:
            return u

        for j in range(self.log - 1, -1, -1):
            if self.up[u][j] != self.up[v][j]:
                u = self.up[u][j]
                v = self.up[v][j]
        return self.up[u][0]

    def distance(self, u, v):
        ancestor = self.lca(u, v)
        return self.depth[u] + self.depth[v] - 2 * self.depth[ancestor]


# Undirected tree example
adj = [[] for _ in range(7)]
edges = [(0, 1), (0, 2), (1, 3),
         (1, 4), (4, 5), (4, 6)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)

solver = BinaryLiftingLCA(adj, root=0)
print("LCA(5, 6):", solver.lca(5, 6))       # 4
print("LCA(3, 5):", solver.lca(3, 5))       # 1
print("distance(3, 6):", solver.distance(3, 6))  # 3

#include <iostream>
#include <vector>
#include <stdexcept>
#include <algorithm>

using namespace std;

class BinaryLiftingLCA {
    int n, LOG;
    vector<int> depth;
    vector<vector<int>> up;

    void checkVertex(int v) const {
        if (v < 0 || v >= n) throw out_of_range("vertex out of range");
    }

public:
    BinaryLiftingLCA(const vector<vector<int>>& adj, int root = 0)
        : n(static_cast<int>(adj.size())) {
        if (n == 0 || root < 0 || root >= n) {
            throw invalid_argument("need a non-empty tree and a valid root");
        }

        LOG = 1;
        while ((1LL << LOG) <= n) ++LOG;
        depth.assign(n, 0);
        vector<int> parent(n, -1), order{root};
        parent[root] = root;

        for (size_t i = 0; i < order.size(); ++i) {
            int u = order[i];
            for (int v : adj[u]) {
                checkVertex(v);
                if (v == u) throw invalid_argument("input contains a self-loop");
                if (v == parent[u]) continue;
                if (parent[v] != -1) throw invalid_argument("input contains a cycle");
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.push_back(v);
            }
        }
        if (static_cast<int>(order.size()) != n) {
            throw invalid_argument("input tree is disconnected");
        }

        up.assign(n, vector<int>(LOG, root));
        for (int v = 0; v < n; ++v) up[v][0] = parent[v];
        for (int j = 1; j < LOG; ++j) {
            for (int v = 0; v < n; ++v) {
                up[v][j] = up[up[v][j - 1]][j - 1];
            }
        }
    }

    int kthAncestor(int v, int k) const {
        checkVertex(v);
        if (k < 0 || k > depth[v]) {
            throw invalid_argument("k must be between 0 and depth[v]");
        }
        for (int j = 0; j < LOG; ++j) {
            if ((k >> j) & 1) v = up[v][j];
        }
        return v;
    }

    int lca(int u, int v) const {
        checkVertex(u);
        checkVertex(v);
        if (depth[u] < depth[v]) swap(u, v);
        u = kthAncestor(u, depth[u] - depth[v]);
        if (u == v) return u;

        for (int j = LOG - 1; j >= 0; --j) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        return up[u][0];
    }

    int distance(int u, int v) const {
        int ancestor = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[ancestor];
    }
};

int main() {
    vector<vector<int>> adj(7);
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {4, 5}, {4, 6}};
    for (auto [u, v] : edges) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    BinaryLiftingLCA solver(adj, 0);
    cout << "LCA(5, 6): " << solver.lca(5, 6) << '\n';       // 4
    cout << "LCA(3, 5): " << solver.lca(3, 5) << '\n';       // 1
    cout << "distance(3, 6): " << solver.distance(3, 6) << '\n'; // 3
    return 0;
}

import java.util.*;

public class BinaryLiftingLCA {
    private final int n, log;
    private final int[] depth;
    private final int[][] up;

    public BinaryLiftingLCA(List<List<Integer>> adj, int root) {
        this.n = adj.size();
        if (n == 0 || root < 0 || root >= n) {
            throw new IllegalArgumentException("need a non-empty tree and a valid root");
        }

        int computedLog = 1;
        while ((1L << computedLog) <= n) computedLog++;
        this.log = computedLog;
        this.depth = new int[n];
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        parent[root] = root;

        List<Integer> order = new ArrayList<>();
        order.add(root);
        for (int i = 0; i < order.size(); i++) {
            int u = order.get(i);
            for (int v : adj.get(u)) {
                checkVertex(v);
                if (v == u) throw new IllegalArgumentException("input contains a self-loop");
                if (v == parent[u]) continue;
                if (parent[v] != -1) {
                    throw new IllegalArgumentException("input contains a cycle");
                }
                parent[v] = u;
                depth[v] = depth[u] + 1;
                order.add(v);
            }
        }
        if (order.size() != n) {
            throw new IllegalArgumentException("input tree is disconnected");
        }

        this.up = new int[n][log];
        for (int v = 0; v < n; v++) up[v][0] = parent[v];
        for (int j = 1; j < log; j++) {
            for (int v = 0; v < n; v++) {
                up[v][j] = up[up[v][j - 1]][j - 1];
            }
        }
    }

    private void checkVertex(int v) {
        if (v < 0 || v >= n) throw new IndexOutOfBoundsException("vertex out of range");
    }

    public int kthAncestor(int v, int k) {
        checkVertex(v);
        if (k < 0 || k > depth[v]) {
            throw new IllegalArgumentException("k must be between 0 and depth[v]");
        }
        for (int j = 0; j < log; j++) {
            if (((k >> j) & 1) == 1) v = up[v][j];
        }
        return v;
    }

    public int lca(int u, int v) {
        checkVertex(u);
        checkVertex(v);
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }
        u = kthAncestor(u, depth[u] - depth[v]);
        if (u == v) return u;

        for (int j = log - 1; j >= 0; j--) {
            if (up[u][j] != up[v][j]) {
                u = up[u][j];
                v = up[v][j];
            }
        }

        return up[u][0];
    }

    public int distance(int u, int v) {
        int ancestor = lca(u, v);
        return depth[u] + depth[v] - 2 * depth[ancestor];
    }

    public static void main(String[] args) {
        int n = 7;
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());

        int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {4, 5}, {4, 6}};
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);
        }

        BinaryLiftingLCA solver = new BinaryLiftingLCA(adj, 0);
        System.out.println("LCA(5, 6): " + solver.lca(5, 6));       // 4
        System.out.println("LCA(3, 5): " + solver.lca(3, 5));       // 1
        System.out.println("distance(3, 6): " + solver.distance(3, 6)); // 3
    }
}

Real-World Applications

Phylogenetic trees

For a rooted evolutionary tree, LCA identifies the most recent represented ancestor shared by two taxa. Root-distance values can then express evolutionary distance along the tree.

The mathematical model must truly be a tree; reticulate evolution may require a network model.

Filesystems and DOM trees

The LCA of two files is their deepest common directory. The LCA of two DOM nodes is their lowest shared container, useful for selections, layout scopes, and tree-diff operations.

Organizational hierarchies

Queries such as “lowest manager responsible for both employees” map directly to LCA when each person has exactly one parent in the hierarchy.

Version history—with a caveat

A merge base resembles an LCA, but Git history is generally a directed acyclic graph because commits may have multiple parents. Ordinary tree-LCA code applies only to a tree-shaped history; DAG merge-base logic is a generalization.

Exercises

Build and trace the jump table

For the tree in the first SVG, write up[v][0], up[v][1], and up[v][2] for vertices 9 and 10.
Trace $LCA(9,7)$ from largest jump to smallest. Mark every proposed jump as accepted or rejected.
Explain why $LCA(2,9)=2$ is returned immediately after depth equalization.

The root is its own ancestor in the implementation, so jumps above it remain at the root.

Connect Euler tours to queries

Using the third SVG, find $LCA(4,5)$ and $LCA(6,7)$ by taking a minimum over the correct first-occurrence intervals.
Prove that consecutive depths in the Euler array differ by exactly 1.
Implement Euler tour plus a sparse table and compare its answers against binary lifting on 1,000 random trees.

Store indices in the sparse table, comparing them by Euler depth, so the RMQ result can map directly back to a vertex.

Derive path utilities

Implement kthVertexOnPath(u, v, k), where $k=0$ returns $u$ and $k=dist(u,v)$ returns $v$.
For a weighted tree, store root-distance sums and verify the weighted distance formula on negative as well as positive edge weights. Why are negative weights harmless in a tree?
Challenge: support online insertion of leaves by computing one new jump-table row per inserted vertex.

Limitations

Pitfall	Consequence	Repair
The graph is not a tree	Vertices may have several root paths or none, so tree ancestors are not well-defined.	Validate connectedness and acyclicity; use a DAG-specific notion when multiple parents are allowed.
Queries span a forest	Vertices in different components have no common ancestor.	Track component IDs, or attach component roots to a virtual super-root only if that artificial answer is meaningful.
The root changes	Ancestor relationships—and therefore LCAs—may change even though the undirected edges do not.	Preprocess for the intended root or use a rerooting identity designed for these queries.
Edges are inserted or removed	Depths and jump entries can become stale.	Leaf-only insertion is manageable; general dynamic forests need structures such as link-cut trees.
The tree is a long chain	A recursive DFS may overflow the call stack.	Use iterative preprocessing, as in the implementations above.
Memory is tight	Binary lifting and sparse tables both use $O(N\log N)$ words.	Consider offline Tarjan LCA or a linear-space RMQ method.

Static preprocessing is a contract

Fast LCA queries rely on a fixed rooted structure. If the graph, component membership, or chosen root changes, the stored depths and ancestors must still match that new interpretation before queries are safe.

Cookie Consent

Lowest Common Ancestor (LCA)

Contents

The Problem Behind LCA

LCA is a preprocessing trade-off

Ancestor Intuition: Where Two Root Paths Merge

The root is part of the input

Ancestor cases are ordinary cases

Working Principle: Binary Lifting

Why scan simultaneous jumps from large to small?

Euler Tour + Range Minimum Query

Sparse table versus linear-space ±1 RMQ

Worked Binary-Lifting Trace

Why the Algorithms Are Correct

Binary lifting

1. Equalization preserves the answer

2. Accepted paired jumps stay below it

3. Rejected jumps fence in the answer

4. One final edge reaches it

Euler tour plus RMQ

Useful Query Recipes Built on LCA

Unweighted distance

Weighted distance

K-th ancestor

Does x lie on path u-v?

Depth is not weighted distance

Complexity and Method Selection

Implementation

Real-World Applications

Phylogenetic trees

Filesystems and DOM trees

Organizational hierarchies

Version history—with a caveat

Exercises

Build and trace the jump table

Connect Euler tours to queries

Derive path utilities

Limitations

Static preprocessing is a contract

Cookie Consent

Lowest Common Ancestor (LCA)

Contents

The Problem Behind LCA

LCA is a preprocessing trade-off

Ancestor Intuition: Where Two Root Paths Merge

The root is part of the input

Ancestor cases are ordinary cases

Working Principle: Binary Lifting

Why scan simultaneous jumps from large to small?

Euler Tour + Range Minimum Query

Sparse table versus linear-space ±1 RMQ

Worked Binary-Lifting Trace

Why the Algorithms Are Correct

Binary lifting

1. Equalization preserves the answer

2. Accepted paired jumps stay below it

3. Rejected jumps fence in the answer

4. One final edge reaches it

Euler tour plus RMQ

Useful Query Recipes Built on LCA

Unweighted distance

Weighted distance

K-th ancestor

Does x lie on path u-v?

Depth is not weighted distance

Complexity and Method Selection

Implementation

Real-World Applications

Phylogenetic trees

Filesystems and DOM trees

Organizational hierarchies

Version history—with a caveat

Exercises

Build and trace the jump table

Connect Euler tours to queries

Derive path utilities

Limitations

Static preprocessing is a contract

Related Deep Dives

Graph Theory Series

Part 11: Trees & Minimum Spanning Trees

Heavy-Light Decomposition (HLD)