Maximum sum of nodes in Binary tree such that no two are adjacent | Dynamic Programming | Function to find the diameter of the tree using Dynamic Programming ; Traverse for all children of node ; Call DFS function again ; Include the current node then donot include the children ; Donot include current node , then include children or not include them ; Recurrence value ; Driver code ; Constructed tree is 1 / \ 2 3 / \ 4 5 ; create undirected edges ; Numbers to node ; Find maximum sum by calling function
def dfs ( node , parent , dp1 , dp2 , adj , tree ) : NEW_LINE INDENT sum1 = 0 NEW_LINE sum2 = 0 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 , tree ) ; NEW_LINE sum1 += dp2 [ i ] ; NEW_LINE sum2 += max ( dp1 [ i ] , dp2 [ i ] ) ; NEW_LINE DEDENT dp1 [ node ] = tree [ node ] + sum1 ; NEW_LINE dp2 [ node ] = sum2 ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT n = 5 ; 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 tree = [ 0 for i in range ( n + 1 ) ] ; NEW_LINE tree [ 1 ] = 10 ; NEW_LINE tree [ 2 ] = 5 ; NEW_LINE tree [ 3 ] = 11 ; NEW_LINE tree [ 4 ] = 6 ; NEW_LINE tree [ 5 ] = 8 ; NEW_LINE dp1 = [ 0 for i in range ( n + 1 ) ] ; NEW_LINE dp2 = [ 0 for i in range ( n + 1 ) ] ; NEW_LINE dfs ( 1 , 1 , dp1 , dp2 , adj , tree ) ; NEW_LINE print ( " Maximum ▁ sum : " , max ( dp1 [ 1 ] , dp2 [ 1 ] ) ) NEW_LINE DEDENT