Last Updated: 7 Feb, 2021
Maximum Sum Of Nodes
Moderate
Asked in companies
You have been given a binary tree with an integer value associated to each node. You are supposed to choose a subset of these nodes such that the sum of these chosen nodes is maximum. Keep in mind that no two of the chosen nodes must be adjacent to each other.
Note :
Two nodes are said to be adjacent to each other if they are directly connected to each other. This means that if a node is taken as part of the sum, then none of its children can be considered for the same and vice versa.
For example :
For the given binary tree
Nodes used in consideration for maximum sum such that no two of them are adjacent are highlighted. Maximum sum of nodes = 1 + 1 + 1 + 4 + 5 = 12.
Input Format :
The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.
The first line of each test case contains elements of the tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.
For example, the input for the tree depicted in the below image would be :
Input Format :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node(of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null(-1).
Note :
The above format was just to provide clarity on how the input is formed for a given tree.
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
Output Format :
For each test case, print the maximum sum of nodes keeping the above constraints in mind.
Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. You just need to return the maximum sum of nodes.
Constraints :
1 <= T <= 100
0 <= N <= 3000
1 <= data <= 10^4
Where ‘T’ is the number of test cases, and ‘N’ is the total number of nodes in the binary tree, and “data” is the value of the binary tree node.
Time Limit : 1 sec
Approaches
Keeping in mind the fact that both node and its children can not be considered for the maximum sum at the same time, we know that if we take a node into our sum, then we will directly call recursively for its grandchildren, OR if we don't take the node into our consideration, we will call for its child nodes and finally consider the maximum sum from both these results.
Considering the above idea, we now think about making a working approach to this problem. The drawbacks of the above idea are that it can lead to solving the same subproblems multiple times.
For example: Consider this binary tree:
Now, here when we choose the root node ‘1’, it will call its grandchild nodes ‘4’ and ‘5’. Similarly when we move to child node ‘3’ and do not select it, then again the nodes ‘4’ and ‘5’ will be called child nodes of ‘3’. This leads to processing nodes ‘4’ and ‘5’ more than once.
In order to stop solving these nodes more than one time, we will memorize the result at each node.
In order to solve this problem, we will use an unordered_map for memoizing the result which stores the result of the complete subtree rooted at a node in the unordered_map, so that if we call the same node again, instead of calculating the value again, we can directly return the value stored in the map.
Algorithm:
- Create a function that returns the maximum sum of nodes from the subset of nodes of the Binary tree under certain given conditions. Create an unordered_map that stores the result of subtree sum.
- Create a function that returns maximum sum rooted at a certain node ‘node’
- If the node = 0, simply return 0
- Check if node is already processed:
- If yes, return the calculated value from the map
- If no, move forward
- Take the current node value and recursively call for all its grandchild nodes and store the value in a variable say “node_included”
- Now, don’t take the current node value and hence, recursively call for all its child nodes and store it in a separate variable say “node_not_included”
- Now, finally choose the maximum of “node_included” and “node_not_included” values and store it in the map.
- Return map.
The idea of this approach is to use a pair for each node. The first value of the pair will store the sum when the current node is included, meaning child nodes are not included. While the second value of the pair will store the sum when the current node is not included, meaning the child nodes are included. Finally, return the maximum of both first and second values.
Algorithm:
- Create a pair that stores the values of the root node.
- Create a function that returns a pair containing two values.
- One from including node.
- One from not including node.
- For the first value: The node is included, meaning both the child nodes are not included.
- For the second value: Do not include the node meaning the child nodes are included.
- Return the maximum of both these values.