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.

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

Question

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.

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.

Accepted Answer

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.

Space Complexity: O(n)Explanation:

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).

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number of nodes in binary tree.

'''





def sumAtKthLevel(root, k):



    # Since there is nothing present return 0;

    if root == None:

        return 0



    # We have reached the Kth level.

    if k == 1:

        return root.data



    sumFromLeft = sumAtKthLevel(root.left, k - 1)

    sumFromRight = sumAtKthLevel(root.right, k - 1)



    return (sumFromLeft + sumFromRight)

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number of nodes in binary tree.

*/



public class Solution {



    public static int sumAtKthLevel(TreeNode root, int k) {



        // Since there is nothing present return 0;

        if (root == null) {

            return 0;

        }



        // We have reached the Kth level.

        if (k == 1) {

            return root.data;

        }



        int sumFromLeft = sumAtKthLevel(root.left, k - 1);

        int sumFromRight = sumAtKthLevel(root.right, k - 1);



        return (sumFromLeft + sumFromRight);

    }



}

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where 'N' is the number of nodes in binary tree.

*/



int sumAtKthLevel(BinaryTreeNode* root, int k)

{

	// Since there is nothing present return 0;

	if (root == NULL)

	{

		return 0;

	}



	// We have reached the Kth level.

	if (k == 1)

	{

		return root -> data;

	}



	int sumFromLeft = sumAtKthLevel(root -> left, k - 1);

	int sumFromRight = sumAtKthLevel(root -> right, k - 1);

	

	return (sumFromLeft + sumFromRight);

}

Accepted Answer

Level Order Traversal

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.

Space Complexity: O(n)Explanation:

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

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

Time Complexity: O(n)Explanation:

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).

Python (3.5)

'''

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number of nodes in binary tree.

'''



import queue



def sumAtKthLevel(root, k):



    que = queue.Queue()



    sum = 0



    if root != None:

        # Using queue for level order traversal.

        que.put(root)





    while (que.empty() is False):

        

        # Reduce the level by 1.

        k -= 1

        sz = que.qsize()



        for i in range(sz):

            curNode = que.get()



            if k == 0:

                currData = curNode.data

                sum += currData



            if (curNode.left != None):

                que.put(curNode.left)



            if (curNode.right != None):

                que.put(curNode.right)





    return sum

Java (SE 1.8)

/*

    Time Complexity : O(N)

    Space Complexity : O(N)



    Where 'N' is the number of nodes in binary tree.

*/



import java.util.Queue;

import java.util.LinkedList;



public class Solution {



    public static int sumAtKthLevel(TreeNode root, int k) {



        Queue> que = new LinkedList>();



        int sum = 0;

        if (root != null) {

            // Using queue for level order traversal.

            que.add(root);



        }



        while (!que.isEmpty()) {

            // Reduce the level by 1.

            k--;

            int sz = que.size();



            for (int i = 0 ; i < sz ; i++) {

                TreeNode curNode = que.poll();



                if (k == 0) {

                    int currData = curNode.data;

                    sum += currData;

                }



                if (curNode.left != null) {

                    que.add(curNode.left);

                }



                if (curNode.right != null) {

                    que.add(curNode.right);

                }

            }

        }



        return sum;

    }



}

C++ (g++ 5.4)

/*

	Time Complexity : O(N)

	Space Complexity : O(N)



	Where 'N' is the number of nodes in binary tree.

*/



int sumAtKthLevel(BinaryTreeNode* root, int k)

{

	queue* > que;



	int sum = 0;

	

	// Using queue for level order traversal.

	que.push(root);



	while (!que.empty())

	{

		// Reduce the level by 1.

		k--;

		int sz = que.size();



		for (int i = 0 ; i < sz ; i++)

		{

			BinaryTreeNode* curNode = que.front();

			que.pop();



			if (k == 0)

			{

				sum = (sum + curNode -> data);

			}



			if (curNode -> left != NULL)

			{

				que.push(curNode -> left);

			}



			if (curNode -> right != NULL)

			{

				que.push(curNode -> right);

			}

		}

	}



	return sum;

}

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:

Example:

Input Format:

Constraints:

Output Format :

Note:

Top Accenture Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern

Top HR questions asked in Accenture Software Developer Intern