Lowest Common Ancestor for a Set of Nodes in a Rooted Tree | C ++ Program to find the LCA in a rooted tree for a given set of nodes ; Set time 1 initially ; Case for root node ; In - time for node ; Out - time for the node ; level [ i ] -- > Level of node i ; t_in [ i ] -- > In - time of node i ; t_out [ i ] -- > Out - time of node i ; Fill the level , in - time and out - time of all nodes ; To find minimum in - time among all nodes in LCA set ; To find maximum in - time among all nodes in LCA set ; Node with same minimum and maximum out time is LCA for the set ; Take the minimum level as level of LCA ; If i - th node is at a higher level than that of the minimum among the nodes of the given set ; Compare in - time , out - time and level of i - th node to the respective extremes among all nodes of the given set ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int T = 1 ; void dfs ( int node , int parent , vector < int > g [ ] , int level [ ] , int t_in [ ] , int t_out [ ] ) { if ( parent == -1 ) { level [ node ] = 1 ; } else { level [ node ] = level [ parent ] + 1 ; } t_in [ node ] = T ; for ( auto i : g [ node ] ) { if ( i != parent ) { T ++ ; dfs ( i , node , g , level , t_in , t_out ) ; } } T ++ ; t_out [ node ] = T ; } int findLCA ( int n , vector < int > g [ ] , vector < int > v ) { int level [ n + 1 ] ; int t_in [ n + 1 ] ; int t_out [ n + 1 ] ; dfs ( 1 , -1 , g , level , t_in , t_out ) ; int mint = INT_MAX , maxt = INT_MIN ; int minv = -1 , maxv = -1 ; for ( auto i = v . begin ( ) ; i != v . end ( ) ; i ++ ) { if ( t_in [ * i ] < mint ) { mint = t_in [ * i ] ; minv = * i ; } if ( t_out [ * i ] > maxt ) { maxt = t_out [ * i ] ; maxv = * i ; } } if ( minv == maxv ) { return minv ; } int lev = min ( level [ minv ] , level [ maxv ] ) ; int node , l = INT_MIN ; for ( int i = 1 ; i <= n ; i ++ ) { if ( level [ i ] > lev ) continue ; if ( t_in [ i ] <= mint && t_out [ i ] >= maxt && level [ i ] > l ) { node = i ; l = level [ i ] ; } } return node ; } int main ( ) { int n = 10 ; vector < int > g [ n + 1 ] ; g [ 1 ] . push_back ( 2 ) ; g [ 2 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 3 ) ; g [ 3 ] . push_back ( 1 ) ; g [ 1 ] . push_back ( 4 ) ; g [ 4 ] . push_back ( 1 ) ; g [ 2 ] . push_back ( 5 ) ; g [ 5 ] . push_back ( 2 ) ; g [ 2 ] . push_back ( 6 ) ; g [ 6 ] . push_back ( 2 ) ; g [ 3 ] . push_back ( 7 ) ; g [ 7 ] . push_back ( 3 ) ; g [ 4 ] . push_back ( 10 ) ; g [ 10 ] . push_back ( 4 ) ; g [ 8 ] . push_back ( 7 ) ; g [ 7 ] . push_back ( 8 ) ; g [ 9 ] . push_back ( 7 ) ; g [ 7 ] . push_back ( 9 ) ; vector < int > v = { 7 , 3 , 8 } ; cout << findLCA ( n , g , v ) << endl ; }