Maximum sum of nodes in Binary tree such that no two are adjacent - GeeksforGeeks
Related: Maximum sum such that no two elements are adjacent
Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that sum of chosen nodes is maximum under a constraint that no two chosen node in subset should be directly connected that is, if we have taken a node in our sum then we can't take its any children in consideration and vice versa.
We can solve this problem by considering the fact that both node and its children can’t be in sum at same time, so when we take a node into our sum we will call recursively for its grandchildren or when we don’t take this node we will call for all its children nodes and finally we will choose maximum from both of these results.
It can be seen easily that above approach can lead to solving same subproblem many times, for example in above diagram node 1 calls node 4 and 5 when its value is chosen and node 3 also calls them when its value is not chosen so these nodes are processed more than once. We can stop solving these nodes more than once by memoizing the result at all nodes.
In below code a map is used for memoizing the result which stores result of complete subtree rooted at a node in the map, so that if it is called again, the value is not calculated again instead stored value from map is returned directly.
Read full article from Maximum sum of nodes in Binary tree such that no two are adjacent - GeeksforGeeks
Related: Maximum sum such that no two elements are adjacent
Given a binary tree with a value associated with each node, we need to choose a subset of these nodes such that sum of chosen nodes is maximum under a constraint that no two chosen node in subset should be directly connected that is, if we have taken a node in our sum then we can't take its any children in consideration and vice versa.
We can solve this problem by considering the fact that both node and its children can’t be in sum at same time, so when we take a node into our sum we will call recursively for its grandchildren or when we don’t take this node we will call for all its children nodes and finally we will choose maximum from both of these results.
It can be seen easily that above approach can lead to solving same subproblem many times, for example in above diagram node 1 calls node 4 and 5 when its value is chosen and node 3 also calls them when its value is not chosen so these nodes are processed more than once. We can stop solving these nodes more than once by memoizing the result at all nodes.
In below code a map is used for memoizing the result which stores result of complete subtree rooted at a node in the map, so that if it is called again, the value is not calculated again instead stored value from map is returned directly.
int sumOfGrandChildren(node* node, map<struct node*, int>& mp){ int sum = 0; // call for children of left child only if it is not NULL if (node->left) sum += getMaxSumUtil(node->left->left, mp) + getMaxSumUtil(node->left->right, mp); // call for children of right child only if it is not NULL if (node->right) sum += getMaxSumUtil(node->right->left, mp) + getMaxSumUtil(node->right->right, mp); return sum;}// Utility method to return maximum sum rooted at node 'node'int getMaxSumUtil(node* node, map<struct node*, int>& mp){ if (node == NULL) return 0; // If node is already processed then return calculated // value from map if (mp.find(node) != mp.end()) return mp[node]; // take current node value and call for all grand children int incl = node->data + sumOfGrandChildren(node, mp); // don't take current node value and call for all children int excl = getMaxSumUtil(node->left, mp) + getMaxSumUtil(node->right, mp); // choose maximum from both above calls and store that in map mp[node] = max(incl, excl); return mp[node];}// Returns maximum sum from subset of nodes// of binary tree under given constraintsint getMaxSum(node* node){ if (node == NULL) return 0; map<struct node*, int> mp; return getMaxSumUtil(node, mp);}