Binary Lifting LCA Depth Overflow Breaks Friend Suggestions

Every time a file system resolves a relative path, every time Git finds the merge-base between two branches, and every time a compiler walks an abstract syntax tree to find scope boundaries — something is quietly computing a Lowest Common Ancestor. LCA isn't an academic curiosity. It's a foundational primitive that powers real systems at scale, and understanding it at depth separates engineers who can solve tree problems on a whiteboard from those who can actually ship the code in production.

The core problem is deceptively simple: given a rooted tree and two nodes u and v, find the deepest node that is an ancestor of both. The naive solution — walk up from both nodes until the paths converge — is O(n) per query and falls apart the moment you have a million-node tree with ten thousand queries per second. That's where the real engineering begins: how do you preprocess the tree so each query becomes O(log n) or even O(1)?

By the end of this article you'll understand three battle-tested approaches to LCA — recursive naive, Euler tour with Sparse Table RMQ, and Binary Lifting — with full runnable Java code for each. You'll know exactly when to reach for each approach, what the preprocessing costs are, and the edge cases that trip up even experienced engineers. Let's dig in.

What is Lowest Common Ancestor (LCA)? — Plain English

The Lowest Common Ancestor (LCA) of two nodes u and v in a tree is the deepest node that is an ancestor of both u and v. Every node is an ancestor of itself, so if u is an ancestor of v, then LCA(u,v) = u.

Real-world use: in a company org chart, LCA of two employees is their common manager. In a file system, LCA of two file paths is their deepest common directory. In computational biology, LCA in an evolutionary tree represents the most recent common ancestor of two species.

The naive approach (walk both nodes up to the root, find the first shared ancestor) takes O(depth) per query. For a balanced tree that is O(log n), but O(n) for a skewed tree. Binary lifting precomputes ancestor pointers so each query runs in O(log n) regardless of tree shape.

How Lowest Common Ancestor (LCA) Works — Step by Step

Naive approach (DFS / path comparison): 1. Find the path from root to u. Find the path from root to v. 2. Walk both paths from the root until they diverge. The last common node is the LCA.

Binary lifting (O(n log n) preprocessing, O(log n) per query): 1. Root the tree. Run a DFS to compute depth[v] and parent[v][0] (direct parent) for all nodes. 2. Compute parent[v][j] = parent[parent[v][j-1]][j-1]: the 2^j-th ancestor of v. 3. To find LCA(u, v): a. If depth[u] < depth[v], swap them so u is deeper. b. Lift u up by (depth[u] - depth[v]) steps to equalize depths. c. If u == v, return u (v is an ancestor of u or vice versa). d. Binary-lift both u and v simultaneously: for j from LOG-1 down to 0, if parent[u][j] != parent[v][j], set u = parent[u][j], v = parent[v][j]. e. Return parent[u][0] (the direct parent of both).

Binary Lifting Deep Dive — The 2^j-th Ancestor Table

The core idea of binary lifting is to precompute, for every node v, its ancestors at distances that are powers of two: parent[v][0] (parent), parent[v][1] (grandparent), parent[v][2] (great-great-grandparent), etc. This is done by dynamic programming: once you know parent[v][k], then parent[v][k+1] = parent[ parent[v][k] ][k].

Why does this work? Because ancestors are transitive: the 2^(k+1)-th ancestor of v is the 2^k-th ancestor of the 2^k-th ancestor of v. So you can fill the table in O(n log n) using sparse DP.

In the query, you first lift the deeper node to the same depth by decomposing the difference into binary bits. Then, from the highest power down to zero, you check if the 2^j-th ancestors of u and v are different. If they are, you know the LCA is deeper than those nodes, so you climb both up. Finally, the LCA is the direct parent of either node.

This technique is similar to binary search on powers – you're essentially jumping up the tree in exponentially shrinking steps until you land just below the common ancestor.

package io.thecodeforge.tree;

import java.util.*;

public class LcaBinaryLifting {
    private int n;
    private int LOG;
    private int[][] parent; // parent[j][v] = 2^j-th ancestor
    private int[] depth;

    public LcaBinaryLifting(int n, List<int[]> edges, int root) {
        this.n = n;
        this.LOG = (int)(Math.log(n) / Math.log(2)) + 1;
        parent = new int[LOG][n + 1];
        depth = new int[n + 1];
        build(edges, root);
    }

    private void build(List<int[]> edges, int root) {
        // Build adjacency
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph[u].add(v);
            graph[v].add(u);
        }

        // BFS from root to fill depth and parent[0]
        Queue<Integer> q = new ArrayDeque<>();
        boolean[] visited = new boolean[n + 1];
        q.offer(root);
        visited[root] = true;
        parent[0][root] = 0; // root's parent is 0 (sentinel)
        depth[root] = 0;
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    depth[v] = depth[u] + 1;
                    parent[0][v] = u;
                    q.offer(v);
                }
            }
        }

        // Build binary lifting table: parent[j][v] = 2^j-th ancestor
        for (int j = 1; j < LOG; j++) {
            for (int v = 1; v <= n; v++) {
                int mid = parent[j - 1][v];
                parent[j][v] = (mid == 0) ? 0 : parent[j - 1][mid];
            }
        }
    }

    public int query(int u, int v) {
        if (depth[u] < depth[v]) { int tmp = u; u = v; v = tmp; }
        // Lift u to same depth as v
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if ((diff >> j & 1) == 1) {
                u = parent[j][u];
            }
        }
        if (u == v) return u;
        // Lift both until parents meet
        for (int j = LOG - 1; j >= 0; j--) {
            if (parent[j][u] != parent[j][v]) {
                u = parent[j][u];
                v = parent[j][v];
            }
        }
        return parent[0][u];
    }
}

C++ Implementation of Binary Lifting LCA

While Java is common in enterprise backends, C++ dominates competitive programming and systems programming where LCA queries are frequent. The logic is identical: build an adjacency list, run BFS (or iterative DFS) to fill depths and parent[0], then populate the binary lifting table. The query uses the same bit decomposition and parallel climbing. Here's a complete, production-ready C++ implementation that uses iterative BFS for safety on deep trees.

#include <bits/stdc++.h>
using namespace std;

class LCA {
    int n, LOG;
    vector<vector<int>> parent;
    vector<int> depth;
public:
    LCA(int n, vector<vector<int>>& adj, int root) : n(n) {
        LOG = ceil(log2(n)) + 1;
        parent.assign(LOG, vector<int>(n + 1, 0));
        depth.assign(n + 1, 0);
        build(adj, root);
    }

    void build(vector<vector<int>>& adj, int root) {
        queue<int> q;
        vector<bool> visited(n + 1, false);
        q.push(root);
        visited[root] = true;
        parent[0][root] = 0;
        depth[root] = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    depth[v] = depth[u] + 1;
                    parent[0][v] = u;
                    q.push(v);
                }
            }
        }
        for (int j = 1; j < LOG; ++j) {
            for (int v = 1; v <= n; ++v) {
                int mid = parent[j - 1][v];
                parent[j][v] = (mid == 0) ? 0 : parent[j - 1][mid];
            }
        }
    }

    int query(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 & (1 << j)) u = parent[j][u];
        }
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; --j) {
            if (parent[j][u] != parent[j][v]) {
                u = parent[j][u];
                v = parent[j][v];
            }
        }
        return parent[0][u];
    }
};

Worked Example — Tracing the Algorithm

Tree: 1 / \ 2 3 / \ 4 5 / \ 6 7

Depths: 1->0, 2->1, 3->1, 4->2, 5->2, 6->3, 7->3

Query: LCA(4, 7) using naive path method: Path to 4: [1, 2, 4] Path to 7: [1, 2, 5, 7] Walk together: 1 matches 1. 2 matches 2. 4 != 5. Last match = 2. LCA(4, 7) = 2.

Query: LCA(6, 3): Path to 6: [1, 2, 5, 6]. Path to 3: [1, 3]. Step 1: depth[6]=3 > depth[3]=1. Lift 6 by 2 steps: 6->5->2. Step 2: depth equalized at 1. 2 != 3. Step 3: lift both by 1: 2->1, 3->1. Now equal. LCA = 1. LCA(6, 3) = 1.

Using tin and tout Times for O(1) Ancestor Checks

During a DFS traversal, we can assign entry time (tin) and exit time (tout) to each node. A node u is an ancestor of node v if and only if tin[u] <= tin[v] and tout[u] >= tout[v]. This is an O(1) check after a simple O(n) DFS.

This technique is useful not only for LCA but also for subtree queries. For binary lifting LCA, we can use is_ancestor() to handle the case where one node is an ancestor of the other quickly, avoiding the depth-equalization steps.

Here's how to augment the binary lifting preprocessing with tin/tout:

• During the BFS (or DFS) that fills depth and parent[0], also record tin and tout using a timer that increments on entry and exit of each node. For BFS, we need a DFS-like traversal to get correct tin/tout ordering; so we use an iterative DFS (stack) to avoid recursion. Alternatively, we can run a separate DFS.

• The is_ancestor(u, v) function returns true if u is ancestor of v.

• In the LCA query, first check if u is ancestor of v (return u) or v is ancestor of u (return v). This is a fast short-circuit.

This pattern is commonly used in competitive programming to optimize queries when one node is frequently an ancestor of the other.

package io.thecodeforge.tree;

import java.util.*;

public class LcaWithTinTout {
    private int n, LOG, timer;
    private int[][] parent;
    private int[] depth, tin, tout;

    public LcaWithTinTout(int n, List<int[]> edges, int root) {
        this.n = n;
        this.LOG = (int)(Math.log(n) / Math.log(2)) + 1;
        parent = new int[LOG][n + 1];
        depth = new int[n + 1];
        tin = new int[n + 1];
        tout = new int[n + 1];
        timer = 0;
        build(edges, root);
    }

    private void build(List<int[]> edges, int root) {
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph[u].add(v);
            graph[v].add(u);
        }

        // Iterative DFS for tin/tout
        Deque<int[]> stack = new ArrayDeque<>(); // [node, state, parent]
        stack.push(new int[]{root, 0, 0});
        while (!stack.isEmpty()) {
            int[] curr = stack.pop();
            int u = curr[0], state = curr[1], par = curr[2];
            if (state == 0) { // entering
                tin[u] = ++timer;
                depth[u] = (par == 0) ? 0 : depth[par] + 1;
                parent[0][u] = par;
                stack.push(new int[]{u, 1, par});
                for (int v : graph[u]) {
                    if (v == par) continue;
                    stack.push(new int[]{v, 0, u});
                }
            } else { // exiting
                tout[u] = timer;
            }
        }

        // Build binary lifting table
        for (int j = 1; j < LOG; j++) {
            for (int v = 1; v <= n; v++) {
                int mid = parent[j - 1][v];
                parent[j][v] = (mid == 0) ? 0 : parent[j - 1][mid];
            }
        }
    }

    public boolean isAncestor(int u, int v) {
        return tin[u] <= tin[v] && tout[u] >= tout[v];
    }

    public int query(int u, int v) {
        if (isAncestor(u, v)) return u;
        if (isAncestor(v, u)) return v;
        if (depth[u] < depth[v]) { int tmp = u; u = v; v = tmp; }
        int diff = depth[u] - depth[v];
        for (int j = 0; j < LOG; j++) {
            if ((diff >> j & 1) == 1) u = parent[j][u];
        }
        if (u == v) return u;
        for (int j = LOG - 1; j >= 0; j--) {
            if (parent[j][u] != parent[j][v]) {
                u = parent[j][u];
                v = parent[j][v];
            }
        }
        return parent[0][u];
    }
}

Euler Tour + RMQ: O(1) LCA Queries

The Euler tour technique transforms LCA into a Range Minimum Query (RMQ) problem on depths. Perform a DFS (iterative to avoid recursion) and record each node every time we visit it (entering and exiting). This produces an array euler[] of length 2n-1. Also record the index of the first occurrence of each node in euler. To query LCA(u, v), find the positions first[u] and first[v], then query the node with minimum depth in the segment between them (inclusive). Using a Sparse Table for RMQ gives O(1) query time after O(n log n) preprocessing.

This is the fastest known static LCA method. It does not support tree modifications, but for a large static tree with millions of queries, it's the best choice.

Here's a complete Java implementation using iterative DFS and a Sparse Table for RMQ.

package io.thecodeforge.tree;

import java.util.*;

public class LcaEulerRMQ {
    private int n, LOG, timer;
    private int[] euler, depthArr, first;
    private int[][] st; // sparse table for RMQ

    public LcaEulerRMQ(int n, List<int[]> edges, int root) {
        this.n = n;
        euler = new int[2 * n - 1];
        depthArr = new int[2 * n - 1];
        first = new int[n + 1];
        Arrays.fill(first, -1);
        timer = 0;
        buildEuler(edges, root);
        buildSparseTable();
    }

    private void buildEuler(List<int[]> edges, int root) {
        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) graph[i] = new ArrayList<>();
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            graph[u].add(v);
            graph[v].add(u);
        }

        // Iterative DFS
        Deque<int[]> stack = new ArrayDeque<>(); // [node, state, depth, parent]
        stack.push(new int[]{root, 0, 0, 0});
        while (!stack.isEmpty()) {
            int[] top = stack.pop();
            int u = top[0], state = top[1], d = top[2], parent = top[3];
            if (state == 0) {
                euler[timer] = u;
                depthArr[timer] = d;
                if (first[u] == -1) first[u] = timer;
                timer++;
                stack.push(new int[]{u, 1, d, parent});
                for (int v : graph[u]) {
                    if (v == parent) continue;
                    stack.push(new int[]{v, 0, d + 1, u});
                }
            } else {
                if (tf != 0) { // not the root after last child
                    euler[timer] = parent;
                    depthArr[timer] = d - 1;
                    timer++;
                }
            }
        }
    }

    private void buildSparseTable() {
        int m = euler.length;
        LOG = (int)(Math.log(m) / Math.log(2)) + 1;
        st = new int[LOG][m];
        for (int i = 0; i < m; i++) st[0][i] = i;
        for (int j = 1; j < LOG; j++) {
            for (int i = 0; i + (1 << j) <= m; i++) {
                int left = st[j - 1][i];
                int right = st[j - 1][i + (1 << (j - 1))];
                st[j][i] = (depthArr[left] < depthArr[right]) ? left : right;
            }
        }
    }

    private int rmq(int l, int r) {
        int len = r - l + 1;
        int k = (int)(Math.log(len) / Math.log(2));
        int left = st[k][l];
        int right = st[k][r - (1 << k) + 1];
        return (depthArr[left] < depthArr[right]) ? left : right;
    }

    public int query(int u, int v) {
        int l = first[u], r = first[v];
        if (l > r) { int tmp = l; l = r; r = tmp; }
        return euler[rmq(l, r)];
    }
}

Edge Cases and Production Pitfalls

Real-world LCA problems rarely fit textbook examples. Here are the edge cases that cause silent failures in production:

1. Forest (disconnected components): If the tree is actually a forest, LCA is undefined for nodes in different components. Either add a virtual root or check component IDs before querying.
2. Large depth with recursive DFS: Recursion stack overflows in Java around 10k–20k depth depending on JVM settings. Use iterative BFS.
3. Integer overflow in depth: As seen in the production incident, depth can exceed 2^31 – 1 in trees that are in reality linked lists (e.g., file path hierarchy). Use long for depth or clamp after a certain depth.
4. Root not connected to all nodes: Make sure the tree is rooted and the root is correctly passed – a node's parent must be 0 for root, but ensure that other nodes with missing edges don't slip through with parent[0] = 0.
5. Multiple edges between same nodes: The tree definition assumes no cycles and at most one edge between any pair. If there are duplicates, BFS may mark nodes visited early, missing correct parent relationships.
6. Memory exhaustion for very large n: If n is 10^7, LOG ~ 24, memory for int table ~ 800 MB. Consider Euler tour + RMQ (O(n) memory) or a sparse table on depth (O(n log n) but smaller because one array).

Complexity Hierarchy of LCA Approaches

Different LCA methods trade off preprocessing time, memory, and query speed. The following table summarizes the major approaches, including the lesser-known sqrt-decomposition method which provides an intermediate trade-off. For most production systems, the choice is between binary lifting (simple, works with incremental updates) and Euler tour + RMQ (fastest queries).

There is also the Farach-Colton and Bender approach which achieves O(n) preprocessing and O(1) queries using ±1 RMQ, but it's complex and rarely implemented in practice.

For most practical purposes, start with binary lifting for simplicity. If you need maximum query throughput on a static tree, upgrade to Euler tour + Sparse Table.