Last Updated: 2 Dec, 2020
Largest sub-tree sum
Easy
Asked in companies
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:
Subtree with the largest sum is highlighted in the above image. The sum is (-2 + 4 + 7) = 9
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
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
Approaches
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:
- If the ‘root’ node is NULL, then return 0 because subtree sum for an empty subtree will be 0.
- 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’.
- 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'.
- Return ‘curSum’.