Home/Questions/Q 3539
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:53:58-05:00 In: ,

Lowest Common Ancestor: Why Binary Lifting in O(log N) beats naive DFS in high-scale DAGs

In standard coding questions, Lowest Common Ancestor (LCA) in a binary tree is solved with post-order recursive DFS in O(N) time. But in production systems (like corporate organization charts or Git commit graph merges), we need to answer thousands of LCA queries per second on the same immutable tree.

Running an O(N) DFS for each query is way too slow. How does Binary Lifting precompute jump tables to answer any LCA query in O(log N) time?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Anonymous
    Begginer

    When you have multiple online LCA queries on a static tree, the gold standard is Binary Lifting (used in compiler dominance frontiers, distributed network routing, and Git commit histories).

    1. The Core Idea: Powers of 2 Parent Jumps

    Instead of storing only a node’s immediate parent (which forces you to step up the tree one node at a time in $O(N)$), what if every node stored its ancestor at distance $2^0, 2^1, 2^2, 2^3, dots, 2^k$?

    We define a 2D table: up[u][i] = the (2^i)-th ancestor of node u.

    The state transition is pure dynamic programming:

    up[u][i] = up[ up[u][i-1] ][i-1]

    In English: ‘To jump $2^i$ steps up from $u$, first jump $2^{i-1}$ steps up to reach intermediate node $v$, and then from $v$ jump another $2^{i-1}$ steps!’ ($2^{i-1} + 2^{i-1} = 2^i$).

    2. Answering an LCA Query in 2 Steps

    To find the LCA of nodes u and v:

    1. Level the Depths: If depth[u] < depth[v], swap them. Use binary powers to jump u upwards until depth[u] == depth[v] in $O(log N)$ steps. If u == v, they were on the same branch → return u!
    2. Simultaneous Binary Leap: Jump both u and v upwards together using the largest possible power of 2 such that their ancestors are still different (up[u][i] != up[v][i]). When no more jumps can be made, their immediate parent (up[u][0]) is their Lowest Common Ancestor!

    Clean C++20 Implementation

    #include <vector>
#include <cmath>
#include <algorithm>

class TreeLCA {
    int n, max_log;
    std::vector<int> depth;
    std::vector<std::vector<int>> up;

    void dfs(int u, int p, int d, const std::vector<std::vector<int>>& adj) {
        depth[u] = d;
        up[u][0] = p;
        for (int i = 1; i < max_log; ++i) {
            up[u][i] = up[ up[u][i - 1] ][i - 1];
        }
        for (int v : adj[u]) {
            if (v != p) {
                dfs(v, u, d + 1, adj);
            }
        }
    }

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

    int queryLCA(int u, int v) {
        if (depth[u] < depth[v]) std::swap(u, v);

        // Step 1: Bring u and v to same depth
        int diff = depth[u] - depth[v];
        for (int i = 0; i < max_log; ++i) {
            if ((diff >> i) & 1) {
                u = up[u][i];
            }
        }
        if (u == v) return u;

        // Step 2: Jump together
        for (int i = max_log - 1; i >= 0; --i) {
            if (up[u][i] != up[v][i]) {
                u = up[u][i];
                v = up[v][i];
            }
        }
        return up[u][0];
    }
};

    Complexity Breakdown

    • Preprocessing Time: O(N log N) via a single DFS pass.
    • Preprocessing Memory: O(N log N) to store the jump table.
    • Per Query Time: Strictly O(log N). For $N = 1,000,000$, $log_2(1,000,000) pprox 20$ operations. You can evaluate 50,000 queries in a fraction of a second!
    • 0