DP on Trees | Set | Java 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
import java . util . * ; public class Main { static int dfs ( int node , int parent , int [ ] dp1 , int [ ] dp2 , Vector < Vector < Integer > > adj ) { int firstmax = - 1 ; int secondmax = - 1 ; for ( int i = 0 ; i < adj . get ( node ) . size ( ) ; ++ i ) { if ( adj . get ( node ) . get ( i ) == parent ) continue ; dfs ( adj . get ( node ) . get ( i ) , node , dp1 , dp2 , adj ) ; if ( firstmax == - 1 ) { firstmax = dp1 [ adj . get ( node ) . get ( i ) ] ; } else if ( dp1 [ adj . get ( node ) . get ( i ) ] >= firstmax ) { secondmax = firstmax ; firstmax = dp1 [ adj . get ( node ) . get ( i ) ] ; } else if ( dp1 [ adj . get ( node ) . get ( i ) ] > secondmax ) { secondmax = dp1 [ adj . get ( node ) . get ( i ) ] ; } } dp1 [ node ] = 1 ; dp1 [ node ] += firstmax ; if ( secondmax != - 1 ) dp2 [ node ] = 1 + firstmax + secondmax ; return Math . max ( dp1 [ node ] , dp2 [ node ] ) ; } public static void main ( String [ ] args ) { int n = 5 ; Vector < Vector < Integer > > adj = new Vector < Vector < Integer > > ( ) ; for ( int i = 0 ; i < n + 1 ; i ++ ) { adj . add ( new Vector < Integer > ( ) ) ; } adj . get ( 1 ) . add ( 2 ) ; adj . get ( 2 ) . add ( 1 ) ; adj . get ( 1 ) . add ( 3 ) ; adj . get ( 3 ) . add ( 1 ) ; adj . get ( 2 ) . add ( 4 ) ; adj . get ( 4 ) . add ( 2 ) ; adj . get ( 2 ) . add ( 5 ) ; adj . get ( 5 ) . add ( 2 ) ; int [ ] dp1 = new int [ n + 1 ] ; int [ ] dp2 = new int [ n + 1 ] ; for ( int i = 0 ; i < n + 1 ; i ++ ) { dp1 [ i ] = 0 ; dp2 [ i ] = 0 ; } System . out . println ( " Diameter ▁ of ▁ the ▁ given ▁ tree ▁ is ▁ " + dfs ( 1 , 1 , dp1 , dp2 , adj ) ) ; } }