DP on Trees | Set | JavaScript program to find diameter of a tree using DFS . ; Function to find the diameter of the tree using Dynamic Programming ; Store the first maximum and secondmax ; Traverse for all children of node ; Call DFS function again ; Find first max ; Secondmaximum ; Find secondmaximum ; Base case for every node ; if ( firstmax != - 1 ) Add ; Find dp [ 2 ] ; Return maximum of both ; Constructed tree is 1 / \ 2 3 / \ 4 5 ; create undirected edges ; Find diameter by calling function
let diameter = - 1 ; function dfs ( node , parent , dp1 , dp2 , adj ) { let firstmax = - 1 ; let secondmax = - 1 ; for ( let i = 0 ; i < adj [ node ] . length ; ++ i ) { if ( adj [ node ] [ i ] == parent ) continue ; dfs ( adj [ node ] [ i ] , node , dp1 , dp2 , adj ) ; if ( firstmax == - 1 ) { firstmax = dp1 [ adj [ node ] [ i ] ] ; } else if ( dp1 [ adj [ node ] [ i ] ] >= firstmax ) { secondmax = firstmax ; firstmax = dp1 [ adj [ node ] [ i ] ] ; } else if ( dp1 [ adj [ node ] [ i ] ] > secondmax ) { secondmax = dp1 [ adj [ node ] [ i ] ] ; } } dp1 [ node ] = 1 ; dp1 [ node ] += firstmax ; if ( secondmax != - 1 ) dp2 [ node ] = 1 + firstmax + secondmax ; return Math . max ( dp1 [ node ] , dp2 [ node ] ) ; } let n = 5 ; let adj = new Array ( n + 1 ) ; for ( let i = 0 ; i < n + 1 ; i ++ ) { adj [ i ] = [ ] ; } adj [ 1 ] . push ( 2 ) ; adj [ 2 ] . push ( 1 ) ; adj [ 1 ] . push ( 3 ) ; adj [ 3 ] . push ( 1 ) ; adj [ 2 ] . push ( 4 ) ; adj [ 4 ] . push ( 2 ) ; adj [ 2 ] . push ( 5 ) ; adj [ 5 ] . push ( 2 ) ; let dp1 = new Array ( n + 1 ) ; let dp2 = new Array ( n + 1 ) ; dp1 . fill ( 0 ) ; dp2 . fill ( 0 ) ; document . write ( " " + dfs ( 1 , 1 , dp1 , dp2 , adj ) ) ;