on

# Lowest Common Ancestor | Binary Lifting

Follow @sukeesh Follow @sukeeshbabu**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] |
2^{j -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 ++ ){
int to = adj[node][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 2^{j -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][0] = 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][0];
}
```

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