Lowest Common Ancestor (LCA)

A Bit of History

The Lowest Common Ancestor (LCA) problem was first formalized by Aho, Hopcroft, and Ullman in 1973 in the context of string algorithms and data structures. In 1984, Dov Harel and Robert Tarjan made a breakthrough by proving that LCA queries could be answered in \(O(1)\) time after \(O(N)\) preprocessing time, though their original algorithm was notoriously complex. In 2000, Martin Farach-Colton and Michael A. Bender published a famous simplification that reduced LCA to the Range Minimum Query (RMQ) problem over an Euler Tour array using a Sparse Table, making \(O(N)\) preprocessing and \(O(1)\) query time accessible and practical. Meanwhile, Binary Lifting — a dynamic programming technique using powers of two — became the favorite \(O(N \log N)\) preprocessing / \(O(\log N)\) query approach due to its extreme ease of implementation.

Working Principle: Binary Lifting

Binary lifting precomputes a table up[u][j] storing the \(2^j\)-th ancestor of node \(u\). Since any integer depth difference can be uniquely represented as a sum of powers of two (its binary representation), we can jump up the tree in logarithmic steps:

1. Depth Equalization: If node \(u\) is deeper than \(v\), lift \(u\) up by jumping \(2^j\) steps at a time until both nodes are at the same depth.
2. Same Node Check: If \(u == v\) after depth equalization, then \(u\) (or \(v\)) was an ancestor of the other — return \(u\).
3. Simultaneous Jumping: Iterate \(j\) from \(\lfloor \log_2 N \rfloor\) down to 0. Whenever up[u][j] != up[v][j], jump both \(u\) and \(v\) up by \(2^j\) steps. This stops both nodes right below their lowest common ancestor.
4. The LCA is then the immediate parent up[u][0].

Euler Tour + RMQ Reduction

An alternative approach flattens the tree into an array via a DFS traversal (an Euler Tour), recording the node visited at each step and its depth:

1. Record the sequence of visited nodes during a DFS traversal. The array has length \(2N - 1\).
2. For any two nodes \(u\) and \(v\), locate their first occurrences in the Euler Tour array.
3. The LCA of \(u\) and \(v\) corresponds to the node with the **minimum depth** in the range between their first occurrences — reducing LCA to a Range Minimum Query (RMQ) problem!
4. Using a **Sparse Table**, RMQ over static arrays can be answered in \(O(1)\) time after \(O(N \log N)\) preprocessing time.

Worked Example

Consider a tree with root 1, children 2 and 3. Node 2 has child 4; Node 4 has children 5 and 6. To find LCA(5, 3):

• Depth of 5 is 3; depth of 3 is 1. Depth difference is 2.
• Lift node 5 by 2 steps ($2^1 = 2$): up[5][1] = 2. Now both nodes (2 and 3) are at depth 1.
• Compare 2 and 3: up[2][0] = 1 and up[3][0] = 1 (their parents are equal to 1).
• The highest jump where up[2][j] != up[3][j] doesn't exist since they immediately share parent 1. Their LCA is 1.

Correctness

Binary lifting works because any depth difference $d$ can be decomposed into $d = \sum b_i 2^i$ (binary expansion). After equalizing depths, if $u \neq v$, jumping when up[u][j] != up[v][j] guarantees we never jump above or to the LCA prematurely. By the end of the loop, $u$ and $v$ are guaranteed to be direct children of the LCA under different branches.

Complexity Analysis

Comparing the two primary LCA approaches:

Implementation

import math

class BinaryLiftingLCA:
    def __init__(self, n, adj, root=0):
        self.n = n
        self.adj = adj
        self.LOG = math.ceil(math.log2(n)) + 1
        self.depth = [0] * n
        self.up = [[0] * self.LOG for _ in range(n)]
        
        self._dfs(root, root, 0)

    def _dfs(self, u, p, d):
        self.depth[u] = d
        self.up[u][0] = p
        for j in range(1, self.LOG):
            self.up[u][j] = self.up[self.up[u][j - 1]][j - 1]
            
        for v in self.adj[u]:
            if v != p:
                self._dfs(v, u, d + 1)

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

        # Equalize depth
        diff = self.depth[u] - self.depth[v]
        for j in range(self.LOG):
            if (diff >> j) & 1:
                u = self.up[u][j]

        if u == v:
            return u

        # Binary lifting
        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]

# Example Usage
n = 7
adj = [[] for _ in range(n)]
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)

lca_solver = BinaryLiftingLCA(n, adj, root=0)
print("LCA(5, 6):", lca_solver.get_lca(5, 6)) # Output: 4
print("LCA(3, 5):", lca_solver.get_lca(3, 5)) # Output: 1

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

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

    void dfs(int u, int p, int d) {
        depth[u] = d;
        up[u][0] = p;
        for (int j = 1; j < LOG; ++j) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }

public:
    BinaryLiftingLCA(int n, const vector<vector<int>>& adj, int root = 0) 
        : n(n), adj(adj) {
        LOG = ceil(log2(n)) + 1;
        depth.resize(n);
        up.assign(n, vector<int>(LOG));
        dfs(root, root, 0);
    }

    int getLCA(int u, int v) {
        if (depth[u] < depth[v]) swap(u, v);

        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; ++j) {
            if ((diff >> j) & 1) u = up[u][j];
        }

        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 main() {
    int n = 7;
    vector<vector<int>> adj(n);
    vector<pair<int, int>> edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {4, 5}, {4, 6}};
    for (auto p : edges) {
        adj[p.first].push_back(p.second);
        adj[p.second].push_back(p.first);
    }

    BinaryLiftingLCA lca(n, adj, 0);
    cout << "LCA(5, 6): " << lca.getLCA(5, 6) << endl; // 4
    cout << "LCA(3, 5): " << lca.getLCA(3, 5) << endl; // 1
    return 0;
}

import java.util.*;

public class BinaryLiftingLCA {
    private int n, LOG;
    private int[] depth;
    private int[][] up;
    private List<List<Integer>> adj;

    public BinaryLiftingLCA(int n, List<List<Integer>> adj, int root) {
        this.n = n;
        this.adj = adj;
        this.LOG = (int) (Math.ceil(Math.log(n) / Math.log(2))) + 1;
        this.depth = new int[n];
        this.up = new int[n][LOG];
        dfs(root, root, 0);
    }

    private void dfs(int u, int p, int d) {
        depth[u] = d;
        up[u][0] = p;
        for (int j = 1; j < LOG; j++) {
            up[u][j] = up[up[u][j - 1]][j - 1];
        }
        for (int v : adj.get(u)) {
            if (v != p) {
                dfs(v, u, d + 1);
            }
        }
    }

    public int getLCA(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }

        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if (((diff >> j) & 1) == 1) {
                u = up[u][j];
            }
        }

        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 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 lca = new BinaryLiftingLCA(n, adj, 0);
        System.out.println("LCA(5, 6): " + lca.getLCA(5, 6)); // 4
        System.out.println("LCA(3, 5): " + lca.getLCA(3, 5)); // 1
    }
}

Real-World Applications

Exercises

1. Given two nodes $u$ and $v$ in a weighted tree, show how to calculate the distance between them using LCA: $\text{dist}(u, v) = \text{depth}(u) + \text{depth}(v) - 2 \cdot \text{depth}(\text{LCA}(u, v))$.
2. Implement the Euler Tour + Sparse Table (RMQ) reduction for LCA in Python or C++.
3. Prove that Tarjan's Offline LCA algorithm (using Union-Find) answers all $Q$ pre-given LCA queries in $O(N + Q \cdot \alpha(N))$ time.
4. Challenge: Modify Binary Lifting to support online addition of leaf nodes to a dynamic tree.

Limitations