Problem
Submissions
Hints & solutions
Discuss
Convert a binary tree to its sum tree
Easy
0/40
Average time to solve is 15m
Contributed by
15 upvotes
Asked in companies
Problem statement
Given a binary tree of integers, you are supposed to modify the given binary tree to a sum tree where each node value is replaced by the sum of the values of both left and right subtrees in the given tree. The value of leaf nodes is changed to zero.
Example:Below is the example showing the input tree and its sum tree.
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 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. So -1 would not be a part of the tree nodes.
The input for the tree depicted in the below image will 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
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).
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).
3. The value of any node in the tree will not be -1.
For each test case, return the level order traversal of converted binary tree separated by single spaces, for NULL nodes print -1.
You don’t need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 3000
-10^4 <= val <=10^4 and val != -1
Where ‘N’ is the total number of nodes in the binary tree, and 'val' is the value of the binary tree node.
Time limit: 1 sec
Sample Input 1 :
2
1 -2 1 3 1 -1 -1 -1 -1 -1 -1
5 -1 1 -8 4 6 -1 -1 -1 -1 -1
Sample Output 1 :
3 4 0 0 0 -1 -1 -1 -1 -1 -1
3 -1 2 6 0 0 -1 -1 -1 -1 -1
Explanation of Sample Output 1 :
In test case 1,
The level order traversal of the modified tree will be {3, 4, 0, 0, 0, -1, -1, -1, -1, -1, -1} where -1 denotes the null nodes.
In test case 2, the level order traversal of the modified tree will be {3, -1, 2, 6, 0, 0, -1, -1, -1, -1, -1} where -1 denotes the null nodes.
Sample Input 2 :
2
1 2 3 -1 4 5 -1 -1 -1 -1 -1
2 1 3 4 -1 -1 5 -1 -1 -1 -1
Sample Output 2 :
14 4 5 -1 0 0 -1 -1 -1 -1 -1
13 4 5 0 -1 -1 0 -1 -1 -1 -1
Explanation of Sample Output 2 :
In test case 1, the level order traversal of the modified tree will be {14, 4, 5, -1, 0, 0, -1, -1, -1, -1, -1} where -1 denotes the null nodes.
In test case 2, the level order traversal of the modified tree will be {13, 4, 5, 0, -1, -1, 0, -1, -1, -1, -1} where -1 denotes the null nodes.
Hint
Hint 1
Value of each node will become the sum of the values of both left and right subtrees.
Approaches (1)
Approach 1
Recursive Approach
Our very basic intuition is that we are going to traverse the given binary tree, and for each node, we will find the sum of all the values of the nodes which are present in its left and right subtrees, then we replace the node value with the corresponding sum.
The Steps are as follows:
- Traverse a given binary tree.
- While traversing the given binary tree, store the old value of the current node, recursively call for left and right subtrees.
- Now change the value of the current node as the sum of the values returned by the recursive calls of left and right subtrees.
- Finally, return the sum of the new value and value (which is the sum of values in the subtree rooted with this node).
Time Complexity
O(N), where ‘N’ is the number of nodes in the given binary tree.
Since traversing for left and right subtrees and a whole tree in a binary tree takes linear time i.e. O(N) time. 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 the recursion stack can grow to the maximum height of the binary tree. Maximum height can go up to N in the worst case (in case of skewed tree). Thus the overall space complexity will be O(N).
Code Solution
(100% EXP penalty)
Convert a binary tree to its sum tree
C++ (g++ 5.4)
Console