Lowest Common Ancestor

Summary

Lowest Common Ancestor (LCA) is a typical rooted tree related problem.

A simple solution is use dfs to traverse the graph from root to leaves. If at some point it is first time we find out two nodes are in the same subtree, the current node is the LCA. The solution costs O(n) time.

If we need to support a list of queries. The simple solution is not good anymore. A technique we could use here is the Binary Lifting method.

Binary Lifting is actually a Dynamic Programming technique. We define alg[i][k] as the 2^k th parent of node i.

Since 2^k=2^(k-1)+2^(k-1), we have alg[i][k]=alg[alg[i][k-1]][k-1].

constexpr int MAX = 31; // 2^31 nodes

// alg[i][0] = parent[i]
for (int i = 0; i < n; ++i) {
    alg[i][0] = parent[i];
}

// 2^k = 2^k-1 + 2^k-1
// alg[i][k] = alg[alg[i][k-1]][k - 1]
for (int k = 1; k < MAX; ++k) {
    for (int i = 0; i < n; ++i) {
        if (alg[i][k - 1] != -1) {
            alg[i][k] = alg[alg[i][k - 1]][k - 1];
        }
    }
}

The Kth Parent of a Node

int getKthAncestor(int node, int j) {
    for (int k = MAX; k >= 0; --k) {
        if (node != -1 && j >= (1 << k)) {
            j -= (1 << k);
            node = alg[node][k];
        }
    }
    return node != -1? node : -1;
}