# 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] = parent[i]
for (int i = 0; i < n; ++i) {
alg[i] = 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;
}``````