# Lowest Common Ancestor | Binary Lifting

What is LCA?

In graph theory and computer science, the lowest common ancestor (LCA) of two nodes v and w in a tree or directed acyclic graph (DAG) T is the lowest (i.e. deepest) node that has both v and w as descendants, where we define each node to be a descendant of itself (so if v has a direct connection from w, w is the lowest common ancestor).

LCA can be found in logN time with N * logN preprocessing.

Variable Description
L[i] Level of node i
P[i] Parent of node i
LCA[i][j] 2j -th ancestor of node i

## Preprocessing

Finding level and parent of each node using simple dfs

``````void dfs(int node, int par){
L[node] = L[par] + 1;
par[node] = par;
for ( int j = 0 ; j < adj[node].size() ; j ++ ){
if(to != par) dfs(to, node);
}
}
``````

Filling in LCA array

Note: Any non negative number can be uniquely represented as a sum of decreasing powers of 2. This is just a variant of binary representation of a number. For number x, there can be at most log2(x) summands

We need to compute `LCA` table. For computing this value we may use following recursion

``````LCA[i][j] = LCA[LCA[i][j-1]][j-1],  if j > 0
----
LCA[i][j] = P[i],  if j = 0
``````

if j > 0,
LCA[i][j] means 2j -th ancestor of node i, which is nothing but 2(j-1) -th ancestor of node LCA[i][j-1]

By using above recursion, we build LCA array as following

``````void ConstructLCA(int n){
lg = ceil(log2(n));
int i, j;
for ( i = 1 ; i <= n ; i ++ ) LCA[i] = par[i];

for ( i = 1 ; i <= lg ; i ++ ) {
for( j = 1 ; j <= n ; j ++ ) {
if( LCA[j][i-1] ) {
LCA[j][i] = LCA[ LCA[j][i-1] ] [i-1];
}
}
}
}
``````

## Query

So, for every power j of 2, if `LCA[x][j] != LCA[y][j]` then we know that LCA(x, y) is on a higher level and we will continue searching for `LCA(x = LCA[x][j], y = LCA[y][j])`. At the end, both x and y will have the same father, so return P[x]. Let’s see what happens if `L[x] != L[y]`. Assume, without loss of generality, that L[p] < L[q]. We can use the same meta-binary search for finding the ancestor of p situated on the same level with q, and then we can compute the LCA as described below.

``````int getLca(int x, int y){

if(L[x] < L[y]){
swap(x, y);
}

for(int i=lg; i >= 0; i--){
if( LCA[x][i] != 0 && L[LCA[x][i]] >= L[y] ){
x = LCA[x][i];
}
}

if( x == y ){
return x;
}

for(int i = lg ; i >= 0 ; i--){
if( LCA[x][i] != 0 && LCA[x][i] != LCA[y][i] ){
x = LCA[x][i];
y = LCA[y][i];
}
}

return LCA[x];
}
``````

We can observe that this function makes at most `2 * log(H)` operations (H is the height of the tree).

My Implementation in C++
github/sukeesh/Algorithm-Implementations/graphs/LCA/LCAbinarylifting.cpp

Reference Topcoder tutorial