Sqrt ( or Square Root ) Decomposition | Set 2 ( LCA of Tree in O ( sqrt ( height ) ) time ) | Naive Javascrit implementation to find LCA in a tree . ; Stores depth for each node ; Stores first parent for each node ; Marking parent for each node ; Marking depth for each node ; Propogating marking down the tree ; A dummy node ; Precalclating 1 ) depth . 2 ) parent . for each node ; Time Complexity : O ( Height of tree ) recursively jumps one node above till both the nodes become equal ; Driver Code ; Adding edges to the tree
var MAXN = 1001 ; var depth = Array ( MAXN ) ; var parent = Array ( MAXN ) ; var adj = Array . from ( Array ( MAXN ) , ( ) => Array ( ) ) ; function addEdge ( u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function dfs ( cur , prev ) { parent [ cur ] = prev ; depth [ cur ] = depth [ prev ] + 1 ; for ( var i = 0 ; i < adj [ cur ] . length ; i ++ ) if ( adj [ cur ] [ i ] != prev ) dfs ( adj [ cur ] [ i ] , cur ) ; } function preprocess ( ) { depth [ 0 ] = - 1 ; dfs ( 1 , 0 ) ; } function LCANaive ( u , v ) { if ( u == v ) return u ; if ( depth [ u ] > depth [ v ] ) { var temp = u ; u = v ; v = temp ; } v = parent [ v ] ; return LCANaive ( u , v ) ; } for ( var i = 0 ; i < MAXN ; i ++ ) adj [ i ] = [ ] ; addEdge ( 1 , 2 ) ; addEdge ( 1 , 3 ) ; addEdge ( 1 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 2 , 6 ) ; addEdge ( 3 , 7 ) ; addEdge ( 4 , 8 ) ; addEdge ( 4 , 9 ) ; addEdge ( 9 , 10 ) ; addEdge ( 9 , 11 ) ; addEdge ( 7 , 12 ) ; addEdge ( 7 , 13 ) ; preprocess ( ) ; document . write ( " " + LCANaive ( 11 , 8 ) + " " ) ; document . write ( " " + LCANaive ( 3 , 13 ) ) ;