human
Give me a code to maximum sum of nodes in Binary tree such that no two are adjacent and the other steps required given the following:
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"
Solution in Python:
assistant
#Here is code to maximum sum of nodes in Binary tree such that no two are adjacent and the other steps required.
 def dfs ( node , parent , dp1 , dp2 , adj , tree ) :
	sum1 = 0
	sum2 = 0
	for i in adj [ node ] :
		if ( i == parent ) :
			continue ;
		dfs ( i , node , dp1 , dp2 , adj , tree ) ;
		sum1 += dp2 [ i ] ;
		sum2 += max ( dp1 [ i ] , dp2 [ i ] ) ;
	dp1 [ node ] = tree [ node ] + sum1 ;
	dp2 [ node ] = sum2 ;
if __name__ == " _ _ main _ _ " :
	n = 5 ;
	adj = [ [ ] for i in range ( n + 1 ) ]
	adj [ 1 ] . append ( 2 ) ;
	adj [ 2 ] . append ( 1 ) ;
	adj [ 1 ] . append ( 3 ) ;
	adj [ 3 ] . append ( 1 ) ;
	adj [ 2 ] . append ( 4 ) ;
	adj [ 4 ] . append ( 2 ) ;
	adj [ 2 ] . append ( 5 ) ;
	adj [ 5 ] . append ( 2 ) ;
	tree = [ 0 for i in range ( n + 1 ) ] ;
	tree [ 1 ] = 10 ;
	tree [ 2 ] = 5 ;
	tree [ 3 ] = 11 ;
	tree [ 4 ] = 6 ;
	tree [ 5 ] = 8 ;
	dp1 = [ 0 for i in range ( n + 1 ) ] ;
	dp2 = [ 0 for i in range ( n + 1 ) ] ;
	dfs ( 1 , 1 , dp1 , dp2 , adj , tree ) ;
	print ( " Maximum ▁ sum : " , max ( dp1 [ 1 ] , dp2 [ 1 ] ) )