Largest sub-tree sum

Easy
0/40
Average time to solve is 15m
profile
Contributed by
14 upvotes
Asked in companies
OlaAmazonGoogle inc

Problem statement

You have been given a Binary Tree of integers. You are supposed to return the largest subtree sum in the given Binary Tree.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example : 
For the given binary tree:

Example

Subtree with the largest sum is highlighted in the above image. The sum is (-2 + 4 + 7) = 9
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer 'T' which denotes the number of test cases. 

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.
Example: 
The input for the tree depicted in the below image would be :

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Example

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)

1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Note: 
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.

2. The input ends when all nodes at the last level are null(-1).
Output Format: 
For each test case, return an integer which denotes the largest subtree sum in the given binary tree.
Note : 
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 50
0 <= N <= 10000
-10^3 <= data <= 10^3 and data != -1

Where ‘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
Sample Input 1 :
2
1 -2 3 4 7 -9 2 -1 -1 -1 -1 -1 -1 -1 -1
1 2 3 -1 -1 -1 -1
Sample Output 1 :
9
6
Explanation of Sample Input 1 :
 In test case 1,

Example

Subtree with the largest sum is highlighted in the above image. The sum is (-2 + 4 + 7) = 9

In test case 2, the subtree with the largest sum is the tree itself. The sum is (1 + 2 + 3) = 6.
Sample Input 2:
2
-2 -4 1 -5 -1 -1 -1 -1 -1
-10 8 11 -1 -1 -1 -1 -1 -1 -1 -1
Sample Output 2:
1
11
Explanation of Sample Output 2:
In test case 1, the largest subtree sum will be formed by just selecting the node with value 1 and thus the largst subtree sum is 1.

In test case 2, the largest subtree sum will be formed by just selecting the node with value 11 and thus the largst subtree sum is 11.
Hint

Can you think of considering all the subtree sum?

Approaches (1)
Recursive approach

The basic idea of this approach is to use pre-order tree traversal to find the subtree sum of every possible subtree in the given binary tree. The answer to our problem is simply the maximum sum.

 

We know that in the binary tree the root node of any subtree can have at max two child nodes, i.e. we can have two subtrees (left subtree and right subtree). We can easily find the subtree sum by adding the left subtree sum and right subtree sum to the value of the current node. Consider the steps as follows:

 

Let us define a recursive function:

subtreeSum(TreeNode<int> *root, int &maxSum)

which returns the subtree sum of the given subtree rooted at ‘root’ node and a ‘maxSum’ variable is passed by reference to the function which stores the maximum subtree sum.

 

We will initialize the ‘maxSum’ variable with a very large negative number. Then, we will find the largest subtree sum by calling the subtreeSum() function with the root node and ‘maxSum’.

 

The steps are as follows:

 

  1. If the ‘root’ node is NULL, then return 0 because subtree sum for an empty subtree will be 0.
  2. We can break down the subtree sum as the sum of the following values:
    • Recur for the left subtree of root node i.e. subtreeSum(left-child of the root) and store the left subtree sum in ‘leftSum’.
    • Recur for the right subtree of root node i.e. subtreeSum(right-child of the root) and store the right subtree sum in ‘rightSum’.
    • The data value of the root node itself let’s say ‘currNode’.
  3. Store the sum of the above-mentioned values in the ‘curSum’ variable.
    • If the ‘curSum’ value (i.e. current subtree sum) is greater than the ‘maxSum’ (i.e. maximum subtree sum) then, assign 'curSum' to 'maxSum'.
  4. Return ‘curSum’.
Time Complexity

O(N), Where ‘N’ is the number of nodes in the given binary tree.

 

Since we are traversing each node once, Thus the overall time complexity will be O(N).

Space Complexity

O(N), Where ‘N’ is the number of nodes in the given binary tree.

 

Since we are doing a recursive tree traversal and in the worst case (Skewed Trees), all nodes of the given tree can be stored in the call recursive stack. Thus the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Largest sub-tree sum
Full screen
Console