Farthest distance of a Node from each Node of a Tree | JavaScript program to implement the above approach ; Adjacency List to store the graph ; Stores the height of each node ; Stores the maximum distance of a node from its ancestors ; Function to add edge between two vertices ; Insert edge from u to v ; Insert edge from v to u ; Function to calculate height of each Node ; Iterate in the adjacency list of the current node ; Dfs for child node ; Calculate height of nodes ; Increase height ; Function to calculate the maximum distance of a node from its ancestor ; Iterate in the adjacency list of the current node ; Find two children with maximum heights ; Calculate the maximum distance with ancestor for every node ; Calculating for children ; Driver Code ; Calculate height of nodes of the tree ; Calculate the maximum distance with ancestors ; Print the maximum of the two distances from each node
let maxN = 100001 ; let adj = new Array ( maxN ) ; adj . fill ( 0 ) ; let height = new Array ( maxN ) ; height . fill ( 0 ) ; let dist = new Array ( maxN ) ; dist . fill ( 0 ) ; function addEdge ( u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function dfs1 ( cur , par ) { for ( let u = 0 ; u < adj [ cur ] . length ; u ++ ) { if ( adj [ cur ] [ u ] != par ) { dfs1 ( adj [ cur ] [ u ] , cur ) ; height [ cur ] = Math . max ( height [ cur ] , height [ adj [ cur ] [ u ] ] ) ; } } height [ cur ] += 1 ; } function dfs2 ( cur , par ) { let max1 = 0 ; let max2 = 0 ; for ( let u = 0 ; u < adj [ cur ] . length ; u ++ ) { if ( adj [ cur ] [ u ] != par ) { if ( height [ adj [ cur ] [ u ] ] >= max1 ) { max2 = max1 ; max1 = height [ adj [ cur ] [ u ] ] ; } else if ( height [ adj [ cur ] [ u ] ] > max2 ) { max2 = height [ adj [ cur ] [ u ] ] ; } } } let sum = 0 ; for ( let u = 0 ; u < adj [ cur ] . length ; u ++ ) { if ( adj [ cur ] [ u ] != par ) { sum = ( ( max1 == height [ adj [ cur ] [ u ] ] ) ? max2 : max1 ) ; if ( max1 == height [ adj [ cur ] [ u ] ] ) dist [ adj [ cur ] [ u ] ] = 1 + Math . max ( 1 + max2 , dist [ cur ] ) ; else dist [ adj [ cur ] [ u ] ] = 1 + Math . max ( 1 + max1 , dist [ cur ] ) ; dfs2 ( adj [ cur ] [ u ] , cur ) ; } } } let n = 6 ; for ( let i = 0 ; i < adj . length ; i ++ ) adj [ i ] = [ ] ; addEdge ( 1 , 2 ) ; addEdge ( 2 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 5 , 6 ) ; dfs1 ( 1 , 0 ) ; dfs2 ( 1 , 0 ) ; for ( let i = 1 ; i <= n ; i ++ ) document . write ( ( Math . max ( dist [ i ] , height [ i ] ) - 1 ) + " " ) ;