Maximum Subtree Sum

Moderate
0/80
Average time to solve is 15m
profile
Contributed by
13 upvotes
Asked in companies
SamsungAmazonCodenation

Problem statement

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.

altImage

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.
Detailed explanation ( Input/output format, Notes, Images )
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

altImage

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.
Sample Input 1 :
1
6
-5 1 2 1 1 0 3 0 0 0 0 0 0 0
Sample Output 1 :
5
Explanation For Sample Input 1 :
The above test case represents the following tree.

altImage

So if we calculate the subtree sum of all nodes we will get the following answer.
SubtreeSum[-5] = 3
SubtreeSum[1] = 3
SubtreeSum[2] = 5
SubtreeSum[1] = 1
SubtreeSum[1] = 1
SubtreeSum[3] = 3
So the largest subtree sum is 5.
Sample Input 2 :
2
7
10 -3 -3 1 1 1 1 0 0 0 0 0 0 0 0 
1
-1 0 0
Sample Output 2 :
8
-1
Explanation For Sample Output 2 :
In test case 1 , we are given the following tree.

altImage

So if we calculate the subtree sum of all nodes we will get the following answer.
SubtreeSum[10] = 8
SubtreeSum[-3] = -1
SubtreeSum[-3] = -1
SubtreeSum[1] = 1
SubtreeSum[1] = 1
SubtreeSum[1] = 1
SubtreeSum[1] = 1
So the largest subtree sum is 8.

In the second test case we have only one node so there will be only one subtree so we return its value as answer that is we return -1.
Hint

Think of using some extra space for storing nodes of the tree.

Approaches (2)
Brute Force

We will do a preorder traversal of the tree and store all the nodes of the tree in a preorder vector.

 

  1. For doing this we will declare the preorder vector.
  2. We will start our preorder traversal with the root node.
  3. We will insert the current node in the preorder vector.
  4. We will call the preorder traversal of the left child of the current node.
  5. We will call the preorder traversal of the right child of the current node.
  6. Do this until we visit all the nodes.
  7. Declare the answer variable where we will store the answer.
  8. 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.
  9. Return the answer.
Time Complexity

O(N^2), where N is the number of nodes in a tree.

 

Because for each node we are traversing its subtree in a preorder manner which is in O(N) and we have O(N) such nodes, so the overall complexity is O(N^2).

Space Complexity

O(N) , where N is the number of nodes in a tree.

 

Because we are storing all the nodes of the tree in a preorder vector which will take O(N) memory space.

Code Solution
(100% EXP penalty)
Maximum Subtree Sum
Full screen
Console