Dynamic Programming on Trees | Set 2 | Javascript 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
let MAX_NODES = 100 ; let In = new Array ( MAX_NODES ) ; let out = new Array ( MAX_NODES ) ; for ( let i = 0 ; i < MAX_NODES ; i ++ ) { In [ i ] = 0 ; out [ i ] = 0 ; } function dfs1 ( v , u , parent ) { In [ u ] = 0 ; for ( let j = 0 ; j < v [ u ] . length ; j ++ ) { let child = v [ u ] [ j ] ; if ( child == parent ) continue ; dfs1 ( v , child , u ) ; In [ u ] = Math . max ( In [ u ] , 1 + In [ child ] ) ; } } function dfs2 ( v , u , parent ) { let mx1 = - 1 , mx2 = - 1 ; for ( let j = 0 ; j < v [ u ] . length ; j ++ ) { let child = v [ u ] [ j ] ; if ( child == parent ) continue ; if ( In [ child ] >= mx1 ) { mx2 = mx1 ; mx1 = In [ child ] ; } else if ( In [ child ] > mx2 ) mx2 = In [ child ] ; } for ( let j = 0 ; j < v [ u ] . length ; j ++ ) { let child = v [ u ] [ j ] ; if ( child == parent ) continue ; let longest = mx1 ; if ( mx1 == In [ child ] ) longest = mx2 ; out [ child ] = 1 + Math . max ( out [ u ] , 1 + longest ) ; dfs2 ( v , child , u ) ; } } function addEdge ( adj , u , v ) { adj [ u ] . push ( v ) ; adj [ v ] . push ( u ) ; } function printHeights ( v , n ) { dfs1 ( v , 1 , 0 ) ; dfs2 ( v , 1 , 0 ) ; for ( let i = 1 ; i < n ; i ++ ) document . write ( " " + i + " " + Math . max ( In [ i ] , out [ i ] ) + " " ) ; } let V = 12 ; let adj = new Array ( V + 1 ) ; for ( let i = 0 ; i <= V ; i ++ ) adj [ i ] = [ ] ; 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 ) ;