Problem

Submissions

Hints & solutions

Discuss

Sum At Kth Level

Easy

0/40

Average time to solve is 15m

Contributed by

9 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
1 2 3 4 -1 -1 5 -1 -1 -1 -1
2
1 2 3 4 -1 -1 5 -1 -1 -1 -1
3

Sample Output 1:

5
9

Explanation of the Sample Input 1:

For the first test case, the nodes at level 2 are 2 and 3; therefore, their sum will be our answer. 2 + 3 = 5. Therefore the final answer is 5.

For the second test case, the nodes at level 3 are 4 and 5; therefore, their sum will be our answer. 4 + 5 = 9. Therefore the final answer is 9.

Sample Input 2:

2
9 10 11 -1 -1 -1 -1 
1
9 10 11 -1 -1 -1 -1
2

Sample Output 2:

9
21

Hint 1

Hint 2

Will inorder traversal help?

Approaches (2)

Approach 1

Approach 2

Inorder Traversal.

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.

Time Complexity

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

We are traversing the whole binary once. Hence, the overall time complexity is O(N).

Space Complexity

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

We are traversing the whole binary once. Hence, the overall recursive stack made will be equal to the height of the tree. Hence space complexity is O(N).

(100% EXP penalty)

Sum At Kth Level

Console