Maximum sum of nodes in Binary tree such that no two are adjacent | A binary tree node structure ; Utility function to create a new Binary Tree node ; method returns maximum sum possible from subtrees rooted at grandChildrens of node ; call for children of left child only if it is not NULL ; call for children of right child only if it is not NULL ; Utility method to return maximum sum rooted at node ; If node is already processed then return calculated value from map ; take current node value and call for all grand children ; don 't take current node  value and call for all children ; choose maximum from both above calls and store that in map ; Returns maximum sum from subset of nodes of binary tree under given constraints ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . left = None NEW_LINE self . right = None NEW_LINE DEDENT DEDENT def newNode ( data ) : NEW_LINE INDENT temp = Node ( data ) NEW_LINE return temp ; NEW_LINE DEDENT def sumOfGrandChildren ( node , mp ) : NEW_LINE INDENT sum = 0 ; NEW_LINE if ( node . left ) : NEW_LINE INDENT sum += ( getMaxSumUtil ( node . left . left , mp ) + getMaxSumUtil ( node . left . right , mp ) ) ; NEW_LINE DEDENT if ( node . right ) : NEW_LINE INDENT sum += ( getMaxSumUtil ( node . right . left , mp ) + getMaxSumUtil ( node . right . right , mp ) ) ; NEW_LINE DEDENT return sum ; NEW_LINE DEDENT def getMaxSumUtil ( node , mp ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT if node in mp : NEW_LINE INDENT return mp [ node ] ; NEW_LINE DEDENT incl = ( node . data + sumOfGrandChildren ( node , mp ) ) ; NEW_LINE excl = ( getMaxSumUtil ( node . left , mp ) + getMaxSumUtil ( node . right , mp ) ) ; NEW_LINE mp [ node ] = max ( incl , excl ) ; NEW_LINE return mp [ node ] ; NEW_LINE DEDENT def getMaxSum ( node ) : NEW_LINE INDENT if ( node == None ) : NEW_LINE INDENT return 0 ; NEW_LINE DEDENT mp = dict ( ) NEW_LINE return getMaxSumUtil ( node , mp ) ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT root = newNode ( 1 ) ; NEW_LINE root . left = newNode ( 2 ) ; NEW_LINE root . right = newNode ( 3 ) ; NEW_LINE root . right . left = newNode ( 4 ) ; NEW_LINE root . right . right = newNode ( 5 ) ; NEW_LINE root . left . left = newNode ( 1 ) ; NEW_LINE print ( getMaxSum ( root ) ) NEW_LINE DEDENT