Farthest distance of a Node from each Node of a Tree | Java 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
import java . util . * ; class GFG { static final int maxN = 100001 ; @ SuppressWarnings ( " unchecked " ) static Vector < Integer > [ ] adj = new Vector [ maxN ] ; static int [ ] height = new int [ maxN ] ; static int [ ] dist = new int [ maxN ] ; static void addEdge ( int u , int v ) { adj [ u ] . add ( v ) ; adj [ v ] . add ( u ) ; } static void dfs1 ( int cur , int par ) { for ( int u : adj [ cur ] ) { if ( u != par ) { dfs1 ( u , cur ) ; height [ cur ] = Math . max ( height [ cur ] , height [ u ] ) ; } } height [ cur ] += 1 ; } static void dfs2 ( int cur , int par ) { int max1 = 0 ; int max2 = 0 ; for ( int u : adj [ cur ] ) { if ( u != par ) { if ( height [ u ] >= max1 ) { max2 = max1 ; max1 = height [ u ] ; } else if ( height [ u ] > max2 ) { max2 = height [ u ] ; } } } int sum = 0 ; for ( int u : adj [ cur ] ) { if ( u != par ) { sum = ( ( max1 == height [ u ] ) ? max2 : max1 ) ; if ( max1 == height [ u ] ) dist [ u ] = 1 + Math . max ( 1 + max2 , dist [ cur ] ) ; else dist [ u ] = 1 + Math . max ( 1 + max1 , dist [ cur ] ) ; dfs2 ( u , cur ) ; } } } public static void main ( String [ ] args ) { int n = 6 ; for ( int i = 0 ; i < adj . length ; i ++ ) adj [ i ] = new Vector < Integer > ( ) ; addEdge ( 1 , 2 ) ; addEdge ( 2 , 3 ) ; addEdge ( 2 , 4 ) ; addEdge ( 2 , 5 ) ; addEdge ( 5 , 6 ) ; dfs1 ( 1 , 0 ) ; dfs2 ( 1 , 0 ) ; for ( int i = 1 ; i <= n ; i ++ ) System . out . print ( ( Math . max ( dist [ i ] , height [ i ] ) - 1 ) + " ▁ " ) ; } }