Lowest Common Ancestor (LCA)

 Source : 

1. Link 1

2. Link 2 (Part 1 & 2)

Code : 

Application : 

1. Find LCA(u, v) : Given two nodes u & v and we can find their LCA in O(log n).

2. Shortest Distance between two nodes : Shortest distance of (u, v) is -

dist[u] + dist[v] - 2 * dist[LCA(u, v)] 

3. Kth node in the path of (u, v) : At first we will calculate LCA(u, v), then check if the Kth node is in left(u) or right(v) side of LCA. In left side we will search for Kth parent from u if K <= Level[u] - Level[LCA] + 1 nodes exist (including LCA). Else in right side we will search for Level[v] - Level[LCA] - (K - Left) th parent of v. Finding Kth parent from u (same for v) - 

for(int i = 0; (k>>i)!=0; i++) {
    if((k>>i) & 1) {
        u = sparse[i][u];
    }

}

return u;

4. RMQ (min/max) in path (u, v) : See this blog and you will know how we can do min/max query by sparse table in O(log n).

5.LCA of (u, v) after changing the root : Let, a = LCA(u, v), b = LCA(r, u), c = LCA(r, v) and the answer for the query is the one value that is different from other two. 

if(a==b)return c;
else if(b==c)return a;
else if(c==a)return b;

Some Problems : 

1. LCA (straight forward)

2.  DISQUERY  (min & max query)

3. Distance in the Tree (distance between two nodes)

4. Inverse the Problem (MST + LCA)

5. ADAORANG (LCA + Bitset)

6.  QTREE2 (Get Kth Parent)

7. TALCA (Changing Root)

8.  ...

To be continued...