Sum At Kth Level
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.
A binary tree is a tree in which each node has at most 2 children.
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.
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.
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.
You don’t have to print anything, it has already been taken care of. Just implement the function.
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.