Last Updated: 1 Dec, 2020
Sum At Kth Level
Easy
Asked in companies
You are given a ‘root’ of the binary tree, and you have to return the sum of all nodes present at the Kth level from the top. The root node is considered as level 1, and below it is level 2, and so on.
Note:
A binary tree is a tree in which each node has at most 2 children.
Example:
For Example, the root node is given as follows :
‘ROOT’ = 1 2 3 4 -1 -1 5 -1 -1 -1 -1 and ‘K’ = 2, Then the sum of all nodes at K-level will be 5. This is because 2 and 3 are present at level 2 and 2 + 3 = 5. Therefore 5 is the answer.
Input Format:
The first line of input contains a single integer ‘T’, representing the number of test cases or queries to be run.
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.
The second line of each test case contains a single integer ‘K’, which denotes the level.
Constraints:
1 <= ‘T’ <= 10
1 <= ‘N’ <= 1000
0 <= data <= 10^3
0 <= ‘K’ <= ‘N’
Time Limit: 1 sec.
Output Format :
For every test case, print a single line that contains a single integer which denotes the sum of all nodes at the Kth level.
The output of each test case is printed in a separate line.
Note:
You don’t have to print anything, it has already been taken care of. Just implement the function.
Approaches
The idea is to do an inorder traversal of the tree, and at each level, we go down, reduce K by 1, and all the states where K = 1, add that node's value in our answer, and recursively do this for all the nodes at Kth level.
The steps are as follows:
- If the ‘root’ is NULL return 0, since that node does not exist.
- If K is equal to 1, then return current nodes data because the given node is at the Kth level.
- Recursively repeat this for left and right subtrees and store the answer in ‘sumFromLeft’ and ‘sumFromRight’, respectively.
- Finally, return the combined sum of ‘sumFromLeft’ and ‘sumFromRight’ as the final result.
The idea is to use level order traversal and add all nodes at the Kth level.
The steps are as follows:
- Maintain a queue, ‘que’ to do a level order traversal, and maintain a variable ‘sum’, which stores the sum of all nodes at the Kth level.
- Push ‘root’ in the ‘que’.
- While the ‘que’ has nodes:
- Reduce K by 1 to keep track of level.
- Pop all nodes from the queue at the current level.
- If ‘K’ is 0, then we are at the Kth level, add all node’s data to ‘sum’.
- Else add the left and right child of the nodes if their left and right pointer are not NULL, respectively.
- Return ‘sum’ as the final result.