Dynamic Programming on Trees | Set 2 | Java code to find the maximum path length considering any node as root ; Function to pre - calculate the array in [ ] which stores the maximum height when travelled via branches ; Initially every node has 0 height ; Traverse in the subtree of u ; If child is same as parent ; dfs called ; Recursively calculate the max height ; Function to pre - calculate the array ouut [ ] which stores the maximum height when traveled via parent ; Stores the longest and second longest branches ; Traverse in the subtress of u ; Compare and store the longest and second longest ; Traverse in the subtree of u ; If longest branch has the node , then consider the second longest branch ; Recursively calculate out [ i ] ; dfs function call ; Function to print all the maximum heights from every node ; Traversal to calculate in [ ] array ; Traversal to calculate out [ ] array ; Print all maximum heights ; Driver Code ; Initialize the tree given in the diagram ; Function to print the maximum height from every node
import java . io . * ; import java . util . * ; class GFG { static final int MAX_NODES = 100 ; static int in [ ] = new int [ MAX_NODES ] ; static int out [ ] = new int [ MAX_NODES ] ; static void dfs1 ( ArrayList < ArrayList < Integer > > v , int u , int parent ) { in [ u ] = 0 ; for ( int j = 0 ; j < v . get ( u ) . size ( ) ; j ++ ) { int child = v . get ( u ) . get ( j ) ; if ( child == parent ) continue ; dfs1 ( v , child , u ) ; in [ u ] = Math . max ( in [ u ] , 1 + in [ child ] ) ; } } static void dfs2 ( ArrayList < ArrayList < Integer > > v , int u , int parent ) { int mx1 = - 1 , mx2 = - 1 ; for ( int j = 0 ; j < v . get ( u ) . size ( ) ; j ++ ) { int child = v . get ( u ) . get ( j ) ; if ( child == parent ) continue ; if ( in [ child ] >= mx1 ) { mx2 = mx1 ; mx1 = in [ child ] ; } else if ( in [ child ] > mx2 ) mx2 = in [ child ] ; } for ( int j = 0 ; j < v . get ( u ) . size ( ) ; j ++ ) { int child = v . get ( u ) . get ( j ) ; if ( child == parent ) continue ; int longest = mx1 ; if ( mx1 == in [ child ] ) longest = mx2 ; out [ child ] = 1 + Math . max ( out [ u ] , 1 + longest ) ; dfs2 ( v , child , u ) ; } } static void addEdge ( ArrayList < ArrayList < Integer > > adj , int u , int v ) { adj . get ( u ) . add ( v ) ; adj . get ( v ) . add ( u ) ; } static void printHeights ( ArrayList < ArrayList < Integer > > v , int n ) { dfs1 ( v , 1 , 0 ) ; dfs2 ( v , 1 , 0 ) ; for ( int i = 1 ; i < n ; i ++ ) System . out . println ( " The ▁ maximum ▁ height ▁ when ▁ node ▁ " + i + " ▁ is ▁ considered ▁ as ▁ root ▁ is ▁ " + Math . max ( in [ i ] , out [ i ] ) ) ; } public static void main ( String [ ] args ) { int V = 12 ; ArrayList < ArrayList < Integer > > adj = new ArrayList < ArrayList < Integer > > ( V + 1 ) ; for ( int i = 0 ; i < V ; i ++ ) adj . add ( new ArrayList < Integer > ( ) ) ; addEdge ( adj , 1 , 2 ) ; addEdge ( adj , 1 , 3 ) ; addEdge ( adj , 1 , 4 ) ; addEdge ( adj , 2 , 5 ) ; addEdge ( adj , 2 , 6 ) ; addEdge ( adj , 3 , 7 ) ; addEdge ( adj , 7 , 10 ) ; addEdge ( adj , 7 , 11 ) ; addEdge ( adj , 4 , 8 ) ; addEdge ( adj , 4 , 9 ) ; printHeights ( adj , V ) ; } }