LCA for general or n | Maximum number of nodes is 100000 and nodes are numbered from 1 to 100000 ; storing the path from root to node ; pushing current node into the path ; node found ; terminating the path ; This Function compares the path from root to ' a ' & root to ' b ' and returns LCA of a and b . Time Complexity : O ( n ) ; trivial case ; setting root to be first element in path ; calculating path from root to a ; calculating path from root to b ; runs till path 1 & path 2 mathches ; returns the last matching node in the paths ; Driver code ; Number of nodes
let MAXN = 100001 ; let tree = new Array ( MAXN ) ; let path = new Array ( 3 ) ; for ( let i = 0 ; i < 3 ; i ++ ) { path [ i ] = new Array ( MAXN ) ; for ( let j = 0 ; j < MAXN ; j ++ ) { path [ i ] [ j ] = 0 ; } } let flag ; / function dfs ( cur , prev , pathNumber , ptr , node ) { for ( let i = 0 ; i < tree [ cur ] . length ; i ++ ) { if ( tree [ cur ] [ i ] != prev && ! flag ) { path [ pathNumber ] [ ptr ] = tree [ cur ] [ i ] ; if ( tree [ cur ] [ i ] == node ) { flag = true ; path [ pathNumber ] [ ptr + 1 ] = - 1 ; return ; } dfs ( tree [ cur ] [ i ] , cur , pathNumber , ptr + 1 , node ) ; } } } function LCA ( a , b ) { if ( a == b ) return a ; path [ 1 ] [ 0 ] = path [ 2 ] [ 0 ] = 1 ; flag = false ; dfs ( 1 , 0 , 1 , 1 , a ) ; flag = false ; dfs ( 1 , 0 , 2 , 1 , b ) ; let i = 0 ; while ( i < MAXN && path [ 1 ] [ i ] == path [ 2 ] [ i ] ) i ++ ; return path [ 1 ] [ i - 1 ] ; } function addEdge ( a , b ) { tree [ a ] . push ( b ) ; tree [ b ] . push ( a ) ; } for ( let i = 0 ; i < MAXN ; i ++ ) tree [ i ] = [ ] ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 3 , 8 ) ; document . write ( " " + LCA ( 4 , 7 ) + " " ) ; document . write ( " " + LCA ( 4 , 6 ) + " " ) ;