Find farthest node from each node in Tree | Javascript implementation to find the farthest node from each vertex of the tree ; Adjacency list to store edges ; Add edge between U and V in tree ; Edge from U to V ; Edge from V to U ; DFS to find the first End Node of diameter ; Calculating level of nodes ; Go in opposite direction of parent ; Function to clear the levels of the nodes ; Set all value of lvl [ ] to 0 for next dfs ; Set maximum with 0 ; DFS will calculate second end of the diameter ; Calculating level of nodes ; Store the node with maximum depth from end1 ; Go in opposite direction of parent ; Function to find the distance of the farthest distant node ; Storing distance from end1 to node u ; Function to find the distance of nodes from second end of diameter ; Storing distance from end2 to node u ; Joining Edge between two nodes of the tree ; Find the one end of the diameter of tree ; Find the other end of the diameter of tree ; Find the distance to each node from end1 ; Find the distance to each node from end2 ; Comparing distance between the two ends of diameter ; Driver Code ; Function call
let N = 10000 ; let adj = new Array ( N ) ; let lvl = new Array ( N ) ; let dist1 = new Array ( N ) ; let dist2 = new Array ( N ) ; let end = 0 , end2 = 0 , maxi = 0 ; for ( let i = 0 ; i < N ; i ++ ) { lvl [ i ] = 0 ; dist1 [ i ] = - 1 ; dist2 [ i ] = - 1 ; } function AddEdge ( u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function findFirstEnd ( u , p ) { lvl [ u ] = 1 + lvl [ p ] ; if ( lvl [ u ] > maxi ) { maxi = lvl [ u ] ; end1 = u ; } for ( let i = 0 ; i < adj [ u ] . length ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findFirstEnd ( adj [ u ] [ i ] , u ) ; } } } function clear ( n ) { for ( let i = 0 ; i <= n ; i ++ ) { lvl [ i ] = 0 ; } maxi = 0 ; dist1 [ 0 ] = dist2 [ 0 ] = - 1 ; } function findSecondEnd ( u , p ) { lvl [ u ] = 1 + lvl [ p ] ; if ( lvl [ u ] > maxi ) { maxi = lvl [ u ] ; end2 = u ; } for ( let i = 0 ; i < adj [ u ] . length ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findSecondEnd ( adj [ u ] [ i ] , u ) ; } } } function findDistancefromFirst ( u , p ) { dist1 [ u ] = 1 + dist1 [ p ] ; for ( let i = 0 ; i < adj [ u ] . length ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findDistancefromFirst ( adj [ u ] [ i ] , u ) ; } } } function findDistancefromSecond ( u , p ) { dist2 [ u ] = 1 + dist2 [ p ] ; for ( let i = 0 ; i < adj [ u ] . length ; i ++ ) { if ( adj [ u ] [ i ] != p ) { findDistancefromSecond ( adj [ u ] [ i ] , u ) ; } } } function findNodes ( ) { let n = 5 ; AddEdge ( 1 , 2 ) ; AddEdge ( 1 , 3 ) ; AddEdge ( 3 , 4 ) ; AddEdge ( 3 , 5 ) ; findFirstEnd ( 1 , 0 ) ; clear ( n ) ; findSecondEnd ( end1 , 0 ) ; findDistancefromFirst ( end1 , 0 ) ; findDistancefromSecond ( end2 , 0 ) ; for ( let i = 1 ; i <= n ; i ++ ) { let x = dist1 [ i ] ; let y = dist2 [ i ] ; if ( x >= y ) { document . write ( end1 + " " ) ; } else { document . write ( end2 + " " ) ; } } } for ( let i = 0 ; i < N ; i ++ ) { adj [ i ] = [ ] ; } findNodes ( ) ;