LCA for general or n | Sparse Matrix DP approach to find LCA of two nodes ; pre - compute the depth for each node and their first parent ( 2 ^ 0 th parent ) time complexity : O ( n ) ; Dynamic Programming Sparse Matrix Approach populating 2 ^ i parent for each node Time complexity : O ( nlogn ) ; Returning the LCA of u and v Time complexity : O ( log n ) ; Step 1 of the pseudocode ; now depth [ u ] = = depth [ v ] ; Step 2 of the pseudocode ; Driver function ; running dfs and precalculating depth of each node . ; Precomputing the 2 ^ i th ancestor for evey node ; calling the LCA function
var MAXN = 100000 ; var level = 18 ; var tree = Array . from ( Array ( MAXN ) , ( ) => Array ( ) ) ; var depth = Array ( MAXN ) . fill ( 0 ) ; var parent = Array . from ( Array ( MAXN ) , ( ) => Array ( level ) . fill ( - 1 ) ) ; function dfs ( cur , prev ) { depth [ cur ] = depth [ prev ] + 1 ; parent [ cur ] [ 0 ] = prev ; for ( var i = 0 ; i < tree [ cur ] . length ; i ++ ) { if ( tree [ cur ] [ i ] != prev ) dfs ( tree [ cur ] [ i ] , cur ) ; } } function precomputeSparseMatrix ( n ) { for ( var i = 1 ; i < level ; i ++ ) { for ( var node = 1 ; node <= n ; node ++ ) { if ( parent [ node ] [ i - 1 ] != - 1 ) parent [ node ] [ i ] = parent [ parent [ node ] [ i - 1 ] ] [ i - 1 ] ; } } } function lca ( u , v ) { if ( depth [ v ] < depth [ u ] ) { u = u + v ; v = u - v ; u = u - v ; } var diff = depth [ v ] - depth [ u ] ; for ( var i = 0 ; i < level ; i ++ ) if ( ( ( diff >> i ) & 1 ) == 1 ) v = parent [ v ] [ i ] ; if ( u == v ) return u ; for ( var i = level - 1 ; i >= 0 ; i -- ) if ( parent [ u ] [ i ] != parent [ v ] [ i ] ) { u = parent [ u ] [ i ] ; v = parent [ v ] [ i ] ; } return parent [ u ] [ 0 ] ; } function addEdge ( u , v ) { tree [ u ] . push ( v ) ; tree [ v ] . push ( u ) ; } function memset ( value ) { for ( var i = 0 ; i < MAXN ; i ++ ) { for ( var j = 0 ; j < level ; j ++ ) { parent [ i ] [ j ] = - 1 ; } } } memset ( - 1 ) ; var n = 8 ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 3 , 8 ) ; depth [ 0 ] = 0 ; dfs ( 1 , 0 ) ; precomputeSparseMatrix ( n ) ; document . write ( " " + lca ( 4 , 7 ) + " " ) ; document . write ( " " + lca ( 4 , 6 ) + " " ) ;