Last Updated: 9 Jan, 2021
Maximum Subtree Sum
Moderate
Asked in companies
You are given an arbitrary binary tree consisting of N nodes. Your task is to find the largest subtree sum.
Note :
1. The value of any node will not be equal to zero.
2. Subtree of a node X is all the nodes that are below X and X itself.
3. For example in the tree given below, nodes 1, 2 and 3 are in subtree of 1.
4. Subtree sum of X is the sum value of all the nodes in subtree of X.
5. Binary tree is a tree wherein each node has at most two children.
6. Any two nodes may have the same value associated with it.
Input format :
First line of each input has a single integer T, denoting the number of test cases.
First line of each test case contains a single integer N, denoting the number of nodes in the tree.
The second line contains the values of the nodes of the tree in the level order form ( 0 for NULL node) Refer to the example for further clarification.
Example:
Consider the binary tree
The input of the tree depicted in the image above will be like:
1
2 3
4 0 5 6
0 7 0 0 0 0
0 0
Explanation :
7 is the number of nodes
Second-line contains the value of nodes from 1 to 7.
Then the structure of the tree follows.
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 (0)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (0)
Right child of 4 = 7
Left child of 5 = null (0)
Right child of 5 = null (0)
Left child of 6 = null (0)
Right child of 6 = null (0)
Level 5 :
Left child of 7 = null (0)
Right child of 7 = null (0)
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 (0).
Output format :
For each test case print a single integer on a new line, representing the maximum subtree sum.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10^2
1 <= N <= 3*10^3
10^(-9) <= VAL[i] <= 10*(9)
Where 'VAL' denotes the values of nodes in binary tree.
Time Limit : 1 sec.
Approaches
We will do a preorder traversal of the tree and store all the nodes of the tree in a preorder vector.
- For doing this we will declare the preorder vector.
- We will start our preorder traversal with the root node.
- We will insert the current node in the preorder vector.
- We will call the preorder traversal of the left child of the current node.
- We will call the preorder traversal of the right child of the current node.
- Do this until we visit all the nodes.
- Declare the answer variable where we will store the answer.
- We have made the preorder vector now we will iterate it and for each node of the vector, we will find the subtree sum.
- For finding the subtree sum of a node we will traverse its subtree in a preorder manner and add the values of all the nodes in its path.
- If the subtree sum of the current node is greater than the answer then update the answer with the subtree sum of the current node.
- Return the answer.
Initialize an Ans equal to negative infinity where we will store the max subarray sum.
Traverse all the nodes of the tree using preorder traversal.
- If we are at node current then call preorder traversal of left and right child of current.
- Calculate the subtree sum of the current node.
- Subtree sum of the current node is the sum of subtree sum of left and right child and val[current].
- If subtree sum of current is greater than Ans then update and.
- Return subtree sum of the current so that we can calculate subtree sum of its parent.
- When we complete the recursive traversal(or in other words when we return back from the preorder traversal function) return Ans.
- Let's say we have this tree -2 3 4 0 0 0 0.
- Then we will first call preorderTraversal(-2)
- from that, we will first call preorderTraversal(3).
- From there we will calculate SubtreeSum[3] = 3 and update Ans = 3 and we return back to -2.
- We will now call preorderTraversal(4).
- From there we will calculate SubtreeSum[4] = 4 and update Ans = 4 and we return back to -2.
- calculate SubtreeSum[-2] = 3 + 4 + (-2) = 5
- The Ans would be updated to 5
- from that, we will first call preorderTraversal(3).
- We will return back from -2 and print 5