DP on Trees | Set | 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 ; elif dp1 [ i ] > secondmax : Find secondmaximum ; Base case for every node ; if firstmax != - 1 : Add ; Find dp [ 2 ] ; Return maximum of both ; Driver Code ; Constructed tree is 1 / \ 2 3 / \ 4 5 ; create undirected edges ; Find diameter by calling function
def dfs ( node , parent , dp1 , dp2 , adj ) : NEW_LINE INDENT firstmax , secondmax = - 1 , - 1 NEW_LINE for i in adj [ node ] : NEW_LINE INDENT if i == parent : NEW_LINE INDENT continue NEW_LINE DEDENT dfs ( i , node , dp1 , dp2 , adj ) NEW_LINE if firstmax == - 1 : NEW_LINE INDENT firstmax = dp1 [ i ] NEW_LINE DEDENT DEDENT elif dp1 [ i ] >= firstmax : NEW_LINE INDENT secondmax = firstmax NEW_LINE firstmax = dp1 [ i ] NEW_LINE secondmax = dp1 [ i ] NEW_LINE DEDENT dp1 [ node ] = 1 NEW_LINE INDENT dp1 [ node ] += firstmax NEW_LINE DEDENT if secondmax != - 1 : NEW_LINE INDENT dp2 [ node ] = 1 + firstmax + secondmax NEW_LINE DEDENT return max ( dp1 [ node ] , dp2 [ node ] ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n , diameter = 5 , - 1 NEW_LINE adj = [ [ ] for i in range ( n + 1 ) ] NEW_LINE adj [ 1 ] . append ( 2 ) NEW_LINE adj [ 2 ] . append ( 1 ) NEW_LINE adj [ 1 ] . append ( 3 ) NEW_LINE adj [ 3 ] . append ( 1 ) NEW_LINE adj [ 2 ] . append ( 4 ) NEW_LINE adj [ 4 ] . append ( 2 ) NEW_LINE adj [ 2 ] . append ( 5 ) NEW_LINE adj [ 5 ] . append ( 2 ) NEW_LINE dp1 = [ 0 ] * ( n + 1 ) NEW_LINE dp2 = [ 0 ] * ( n + 1 ) NEW_LINE print ( " Diameter ▁ of ▁ the ▁ given ▁ tree ▁ is " , dfs ( 1 , 1 , dp1 , dp2 , adj ) ) NEW_LINE DEDENT