LCA - Lowest Common Ancestor

Hard
0/120
Average time to solve is 40m

Problem statement

The lowest common ancestor (LCA) is a concept in graph theory and computer science.

Let ‘T’ be a rooted tree with ‘N’ nodes. The lowest common ancestor is defined between two nodes, ‘u’ and ‘v’, as the lowest node in ‘T’ that has both ‘u’ and ‘v’ as descendants (where we allow a node to be a descendant of itself). - Wikipedia

For the given tree, The LCA of nodes 5 and 8 will be node 2, as node 2 is the first node that lies in the path from node 5 to root node 1 and from node 8 to root node 1.

Path from node 5 to root node looks like 5 → 2 → 1.

Path from node 8 to root node looks like 8 → 6 → 2 → 1.

Since 2 is the first node that lies in both paths. Hence LCA will be 2.

Given any two nodes ‘u’ and ‘v’, find the LCA for the two nodes in the given Tree ‘T’.

Note: For each test case, the tree is rooted at node 1.

Detailed explanation ( Input/output format, Notes, Images )
Constraints -
``````1<= ‘T' <= 5
1 <= ‘N’ <= 10^5
1 <= ‘Q’ <= 10^5.
1 <= ‘u’, ‘v’ <= ‘N’.

Time Limit: 1 sec
``````
Sample Input-1
``````2
5
1 2
2 3
1 4
2 5
2
3 5
4 5
3
1 2
3 2
2
1 3
2 2
``````
Sample Output-1
``````2 1
1 2
``````
Explanation for Sample Input 1:
``````For test case 1:
``````

``````From the above graph,
we can see that for nodes ‘5’ and ‘3’, ‘2’ is the direct parent of both the nodes. Hence the LCA will be 2.
For nodes ‘4’ and ‘5’,  the first node that has both node 4 and node 5 in its subtree is 1. Hence, ‘1’ is the LCA.
``````
Sample Input-2
``````2
4
1 2
2 3
4 1
2
3 4
4 1
5
1 4
2 4
3 5
5 1
2
2 3
3 4
``````
Sample Output-2
``````1 1
1 1
``````
Console