Lowest Common Ancestor: Multiple Solutions and Complexity Analysis

What is the Lowest Common Ancestor (LCA)?

The Lowest Common Ancestor (LCA) of two nodes in a rooted tree is the deepest node that is an ancestor of both nodes. In other words, it is the node furthest from the root that lies on both paths from the root to each of the two nodes. If you trace the unique simple path from the root to u and the path from the root to v, the LCA is the last node that these two paths have in common before they diverge.

For example, in a binary tree representing a family tree, the LCA of you and your sibling is your parent. In a file system hierarchy, the LCA of two files is the deepest folder that contains both. In version control (like Git), the merge base of two branches is exactly the LCA in the commit history DAG.

Why LCA Matters

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

LCA is a fundamental operation on trees with countless practical applications:

Version control systems (Git merge-base) – determines the common ancestor of two commits to perform a three-way merge.
DOM manipulation / Web development – find the deepest container element that contains two given elements.
Compiler design – in abstract syntax trees, LCA helps in type inference and scope analysis.
Network routing – in hierarchical network topologies, the LCA identifies the nearest common aggregation point.
Bioinformatics – phylogenetic trees use LCA to compare evolutionary relationships.
Game development – scene graphs and bounding volume hierarchies use LCA for collision detection optimization.

Because trees appear everywhere in software, an efficient LCA implementation is an essential tool in any developer's algorithmic toolkit.

Problem Statement

Given a rooted tree with n nodes (typically numbered from 0 to n-1 or 1 to n), and two nodes u and v, find the lowest common ancestor of u and v. The tree is provided either as adjacency lists, parent pointers, or a combination. You may have to answer many such queries (online) or a batch of queries (offline). Solutions differ in preprocessing time, query time, memory, and implementation complexity.

Multiple Solutions and Complexity Analysis

1. Naive Traversal Using Parent Pointers

The simplest approach assumes we have direct access to each node's parent and its depth. If not given, we perform a single DFS/BFS to compute parent[u] and depth[u] for every node. For a query, we first equalize depths by moving the deeper node up until both are at the same depth. Then we move both nodes up together until they meet.

Preprocessing: O(n) time, O(n) space.
Query: O(height) worst-case, which is O(n) for a skewed tree (e.g. a linked list). This is acceptable only if queries are rare and the tree is shallow.


def dfs_parent_and_depth(graph, root):
    n = len(graph)
    parent = [-1] * n
    depth = [0] * n
    stack = [(root, -1)]
    while stack:
        node, p = stack.pop()
        parent[node] = p
        for child in graph[node]:
            if child != p:
                depth[child] = depth[node] + 1
                stack.append((child, node))
    return parent, depth

def lca_naive(u, v, parent, depth):
    # equalize depths
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]
    # move up together
    while u != v:
        u = parent[u]
        v = parent[v]
    return u

# Example usage:
# Tree: 0-1, 0-2, 1-3, 1-4
graph = [[1,2], [0,3,4], [0], [1], [1]]
parent, depth = dfs_parent_and_depth(graph, 0)
print(lca_naive(3, 4, parent, depth))  # Output: 1
print(lca_naive(3, 2, parent, depth))  # Output: 0

2. Binary Lifting (Sparse Table on Ancestors)

Binary lifting precomputes, for each node, its ancestors at powers of two. Define up[node][k] as the 2^k-th ancestor of node. This table has size n × log₂(max_depth). Queries use binary representation to jump up in logarithmic steps.

Preprocessing: O(n log n) time, O(n log n) space.
Query: O(log n) time.

This is the most popular choice for online queries when n is up to ~10⁵ and memory is sufficient. Implementation is straightforward and robust.


import math

class BinaryLiftingLCA:
    def __init__(self, graph, root=0):
        n = len(graph)
        self.parent = [-1] * n
        self.depth = [0] * n
        self.max_log = int(math.ceil(math.log2(n))) + 1
        self.up = [[-1] * self.max_log for _ in range(n)]
        
        # DFS to set parent, depth, and first ancestors
        stack = [(root, -1)]
        while stack:
            node, p = stack.pop()
            self.parent[node] = p
            self.up[node][0] = p  # 2^0 ancestor is parent
            for i in range(1, self.max_log):
                if self.up[node][i-1] != -1:
                    self.up[node][i] = self.up[self.up[node][i-1]][i-1]
                else:
                    self.up[node][i] = -1
            for child in graph[node]:
                if child != p:
                    self.depth[child] = self.depth[node] + 1
                    stack.append((child, node))
        # Note: above loop processes ancestors only after parent is set, but we need to compute up table for each node after its parent's up table is ready.
        # We'll do a proper DFS/BFS with ordering.

    # Better implementation with explicit DFS:
def build_binary_lifting(graph, root=0):
    n = len(graph)
    max_log = int(math.ceil(math.log2(n))) + 1
    up = [[-1] * max_log for _ in range(n)]
    depth = [0] * n
    parent = [-1] * n
    
    # iterative DFS that ensures parent's up table is filled before child
    stack = [(root, -1, 0)]  # node, parent, depth
    order = []
    while stack:
        node, p, d = stack.pop()
        parent[node] = p
        depth[node] = d
        order.append(node)
        for child in graph[node]:
            if child != p:
                stack.append((child, node, d+1))
    
    # Now compute up table in topological order (parents before children)
    for node in order:
        up[node][0] = parent[node]
        for i in range(1, max_log):
            if up[node][i-1] != -1:
                up[node][i] = up[up[node][i-1]][i-1]
            else:
                up[node][i] = -1
    
    return up, depth, max_log

def lca_binary_lifting(u, v, up, depth, max_log):
    if depth[u] < depth[v]:
        u, v = v, u
    # lift u to same depth as v
    diff = depth[u] - depth[v]
    for i in range(max_log):
        if diff & (1 << i):
            u = up[u][i]
    if u == v:
        return u
    # lift both together from high to low power
    for i in range(max_log - 1, -1, -1):
        if up[u][i] != up[v][i]:
            u = up[u][i]
            v = up[v][i]
    return up[u][0]

# Example usage
graph = [[1,2], [0,3,4], [0], [1], [1]]
up, depth, max_log = build_binary_lifting(graph, 0)
print(lca_binary_lifting(3, 4, up, depth, max_log))  # 1
print(lca_binary_lifting(3, 2, up, depth, max_log))  # 0

3. Euler Tour + Range Minimum Query (RMQ)

This technique reduces LCA to a Range Minimum Query (RMQ) problem, which can then be solved using a sparse table for O(1) queries. Perform a depth-first Euler tour: record nodes each time we enter them and when we return from a child. Also record their depths. For any two nodes, their LCA is the node with minimum depth in the Euler tour between their first occurrences. This works because the Euler tour contains the subtree path.

Preprocessing: O(n log n) to build RMQ sparse table (or O(n) if using Cartesian tree + RMQ, but sparse table is simpler).
Query: O(1) after preprocessing.

This method delivers the theoretically fastest online queries. It's ideal when you have many queries and need constant-time answers, and can afford O(n log n) memory.


import math

def euler_tour_lca(graph, root=0):
    n = len(graph)
    euler = []        # sequence of nodes visited
    depth = []        # depth of each node in euler tour
    first = [-1] * n  # index of first occurrence in euler
    d = [0] * n       # node depth
    
    # DFS to build Euler tour
    stack = [(root, -1, 0)]  # node, parent, depth
    while stack:
        node, p, cur_depth = stack.pop()
        d[node] = cur_depth
        if first[node] == -1:
            first[node] = len(euler)
        euler.append(node)
        depth.append(cur_depth)
        for child in reversed(graph[node]):  # reversed to maintain natural order
            if child != p:
                stack.append((node, p, cur_depth))  # after child, we'll come back to node
                stack.append((child, node, cur_depth + 1))
                # The above simulates recursion: push node again, then child.
                # Actually simpler: use explicit recursion or iterative with state.
    return euler, depth, first

# Better iterative approach with explicit "entering" and "returning" events:
def build_euler_tour(graph, root=0):
    n = len(graph)
    euler = []
    depths = []
    first = [-1] * n
    depth = [0] * n
    
    # Use stack with (node, parent, state) where state=0 means entering, state=1 means returning
    stack = [(root, -1, 0)]
    while stack:
        node, parent, state = stack.pop()
        if state == 0:
            # Entering node
            if first[node] == -1:
                first[node] = len(euler)
            euler.append(node)
            depths.append(depth[node])
            # Push return event
            stack.append((node, parent, 1))
            # Push children
            for child in reversed(graph[node]):
                if child != parent:
                    depth[child] = depth[node] + 1
                    stack.append((child, node, 0))
        else:
            # Returning from node (after children)
            if parent != -1:
                euler.append(parent)
                depths.append(depth[parent])
    return euler, depths, first

# Build sparse table for RMQ on depths
class SparseTableRMQ:
    def __init__(self, arr):
        n = len(arr)
        self.log = [0] * (n + 1)
        for i in range(2, n+1):
            self.log[i] = self.log[i // 2] + 1
        max_log = self.log[n] + 1
        self.st = [[0] * max_log for _ in range(n)]
        for i in range(n):
            self.st[i][0] = i  # store index of minimum
        k = 1
        while (1 << k) <= n:
            j = 0
            while j + (1 << k) - 1 < n:
                left_idx = self.st[j][k-1]
                right_idx = self.st[j + (1 << (k-1))][k-1]
                self.st[j][k] = left_idx if arr[left_idx] < arr[right_idx] else right_idx
                j += 1
            k += 1
        self.arr = arr
    
    def query_min_index(self, l, r):
        # r inclusive
        length = r - l + 1
        k = self.log[length]
        left_idx = self.st[l][k]
        right_idx = self.st[r - (1 << k) + 1][k]
        return left_idx if self.arr[left_idx] < self.arr[right_idx] else right_idx

# LCA using Euler + RMQ
class EulerLCA:
    def __init__(self, graph, root=0):
        self.euler, self.depths, self.first = build_euler_tour(graph, root)
        self.rmq = SparseTableRMQ(self.depths)
    
    def lca(self, u, v):
        l = self.first[u]
        r = self.first[v]
        if l > r:
            l, r = r, l
        min_idx = self.rmq.query_min_index(l, r)
        return self.euler[min_idx]

# Example usage
graph = [[1,2], [0,3,4], [0], [1], [1]]
lca_finder = EulerLCA(graph, 0)
print(lca_finder.lca(3, 4))  # 1
print(lca_finder.lca(3, 2))  # 0

4. Tarjan's Offline Algorithm (Union-Find)

For offline queries – when you have a batch of queries known in advance – Tarjan's algorithm provides an almost-linear time solution. It uses a DFS with disjoint-set union (Union-Find) and an "ancestor" tracking array. As the DFS backtracks, unions are performed and queries are answered. The total time is O((n + Q) * α(n)), where α is the inverse Ackermann function (effectively constant).

This is unbeatable asymptotically for offline scenarios, but it's more complex and not suitable for online queries.


class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx == ry:
            return
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1

def tarjan_lca(graph, root, queries):
    """
    graph: adjacency list
    root: root node
    queries: list of pairs (u, v) to answer
    returns: dictionary mapping (u,v) or (v,u) to their LCA
    """
    n = len(graph)
    uf = UnionFind(n)
    ancestor = [-1] * n
    visited = [False] * n
    # Map each node to list of (query_index, other_node) for efficient lookup
    query_map = {i: [] for i in range(n)}
    answers = {}
    
    for idx, (u, v) in enumerate(queries):
        query_map[u].append((idx, v))
        query_map[v].append((idx, u))
        # Normalize pair order for answer storage
        answers[(u, v) if u < v else (v, u)] = None
    
    def dfs(node, parent):
        visited[node] = True
        ancestor[uf.find(node)] = node  # initially ancestor of its set is itself
        for child in graph[node]:
            if child != parent:
                dfs(child, node)
                # Union child's set with node's set
                uf.union(node, child)
                # After union, the ancestor of the new set is node
                ancestor[uf.find(node)] = node
        # Now answer queries where node is one endpoint and the other is visited
        for idx, other in query_map[node]:
            if visited[other]:
                lca_node = ancestor[uf.find(other)]
                # Store answer
                key = (node, other) if node < other else (other, node)
                answers[key] = lca_node
        # Mark node processed (implicitly by visited)
    
    dfs(root, -1)
    return answers

# Example usage
graph = [[1,2], [0,3,4], [0], [1], [1]]
queries = [(3,4), (3,2)]
result = tarjan_lca(graph, 0, queries)
for (u,v) in queries:
    key = (u,v) if u < v else (v,u)
    print(f"LCA({u},{v}) = {result[key]}")

Complexity Comparison Table

Below is a summary of the four methods:

Method	Preprocessing Time	Query Time	Space	Online / Offline	Notes
Naive (parent pointers)	O(n)	O(n) worst-case	O(n)	Online	Simple, only for shallow trees or few queries.
Binary Lifting	O(n log n)	O(log n)	O(n log n)	Online	Good balance; most popular for competitive programming.
Euler Tour + RMQ	O(n log n)	O(1)	O(n log n)	Online	Fastest queries; higher constant factor.
Tarjan Offline	O(n + Q α(n))	N/A (batch)	O(n + Q)	Offline	Best asymptotic for batch; requires all queries upfront.

Best Practices and When to Use Each

Naive approach – Use only if the tree is guaranteed shallow (e.g., binary search trees with small height) or you have a tiny number of queries. Not recommended for production code.
Binary lifting – The sweet spot for most applications. Easy to implement, supports online queries, and logarithmic query time is sufficient for up to millions of queries on trees with ~10⁵ nodes. Memory is usually acceptable (a few megabytes).
Euler Tour + RMQ – Choose when you need the absolute fastest query time (constant) and can afford the memory and slightly more complex implementation. Often used in competitive programming for large query batches.
Tarjan's offline algorithm – Use when you have a known set of queries in advance and want to minimize total time. Also useful in systems that batch-process historical LCA queries (e.g., static analysis tools).
Dynamic trees – None of these methods handle tree modifications efficiently. For dynamic LCA (link/cut operations), consider Link-Cut Trees or Euler Tour Trees with RMQ updates.

When implementing, always consider the tree size and query count. Prefer binary lifting as a default unless you have a strong reason otherwise. Profile and test with realistic data – constant factors can make Euler+RMQ slower than binary lifting for moderate n due to cache inefficiency.

Conclusion

The Lowest Common Ancestor is a classic tree problem that appears in countless domains. We've explored four distinct solutions, each with its own trade-offs between preprocessing, query speed, memory, and complexity. By understanding these methods, you can select the right tool for your specific use case: naive for trivial situations, binary lifting for robust general use, Euler+RMQ for blazing-fast constant queries, and Tarjan's offline algorithm for batch processing with optimal total time. Armed with these implementations and their complexity analysis, you're now equipped to handle LCA problems efficiently in any project.