Lowest Common Ancestor for a Set of Nodes in a Rooted Tree | 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
let T = 1 ; function dfs ( node , parent , g , level , t_in , t_out ) { if ( parent == - 1 ) { level [ node ] = 1 ; } else { level [ node ] = level [ parent ] + 1 ; } t_in [ node ] = T ; for ( let i = 0 ; i < g [ node ] . length ; i ++ ) { if ( g [ node ] [ i ] != parent ) { T ++ ; dfs ( g [ node ] [ i ] , node , g , level , t_in , t_out ) ; } } T ++ ; t_out [ node ] = T ; } function findLCA ( n , g , v ) { let level = new Array ( n + 1 ) ; let t_in = new Array ( n + 1 ) ; let t_out = new Array ( n + 1 ) ; dfs ( 1 , - 1 , g , level , t_in , t_out ) ; let mint = Number . MAX_VALUE , maxt = Number . MIN_VALUE ; let minv = - 1 , maxv = - 1 ; for ( let i = 0 ; i < v . length ; i ++ ) { if ( t_in [ v [ i ] ] < mint ) { mint = t_in [ v [ i ] ] ; minv = v [ i ] ; } if ( t_out [ v [ i ] ] > maxt ) { maxt = t_out [ v [ i ] ] ; maxv = v [ i ] ; } } if ( minv == maxv ) { return minv ; } let lev = Math . min ( level [ minv ] , level [ maxv ] ) ; let node = 0 , l = Number . MIN_VALUE ; for ( let 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 ; } let n = 10 ; let g = new Array ( n + 1 ) ; for ( let i = 0 ; i < g . length ; i ++ ) g [ i ] = [ ] ; g [ 1 ] . push ( 2 ) ; g [ 2 ] . push ( 1 ) ; g [ 1 ] . push ( 3 ) ; g [ 3 ] . push ( 1 ) ; g [ 1 ] . push ( 4 ) ; g [ 4 ] . push ( 1 ) ; g [ 2 ] . push ( 5 ) ; g [ 5 ] . push ( 2 ) ; g [ 2 ] . push ( 6 ) ; g [ 6 ] . push ( 2 ) ; g [ 3 ] . push ( 7 ) ; g [ 7 ] . push ( 3 ) ; g [ 4 ] . push ( 10 ) ; g [ 10 ] . push ( 4 ) ; g [ 8 ] . push ( 7 ) ; g [ 7 ] . push ( 8 ) ; g [ 9 ] . push ( 7 ) ; g [ 7 ] . push ( 9 ) ; let v = [ ] ; v . push ( 7 ) ; v . push ( 3 ) ; v . push ( 8 ) ; document . write ( findLCA ( n , g , v ) + " " ) ;