Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Problem Statement
C++ Implementation
Complexity Analysis
Frequently Asked Questions
What is meant by a Binary tree? 
What is the advantage of using Level order traversal?
What is the other name of Level order traversal?
Last Updated: Mar 27, 2024

Print all K-sum levels in a Binary Tree

Author Yukti Kumari
0 upvote
Roadmap to SDE career at Amazon
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM


Binary trees are one of the most important and useful data structures with various practical applications. 

For example - It is used for data compression in Huffman coding. Also, in database indexing, Binary trees help sort data which makes the operations such as insertion, deletion, and searching quite easier.

In this article, we will discuss a question based on binary trees. You will learn to solve the problem using the algorithms already known to us in binary trees. Like, for this problem, we will be using level order traversal

Without much ado,  let’s get started with the problem statement.

Problem Statement

You are given a Binary Tree and an integer K where the tree has nodes having positive or negative values. Your task is to print all the elements of a level in which the sum of all the elements equals K. If no such level exists, then print “Not Possible”.

Please try to solve this problem on your own before moving on to further discussion here.



1. K=10

The binary tree is given in below figure:


illustration image

The output will be  - 

5   -7   12


2. K=20

Consider the previous binary tree only, but now the value of K is 20. 

What should be the output?

We can see that there is no level with a sum equal to 20. So, the output will be - “Not Possible”.

I hope with these examples you have understood the problem statement precisely.


So, let’s move on to the approach of this problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job


As you can observe, the objective is to traverse the binary tree level by level, and in each level, if the sum of all elements is K, you need to print it.

So, simply we will do level order traversal and process the level accordingly.


The steps are as follows:

  1. Declare a boolean variable flag and initialize flag=false. The flag variable determines whether there is at least one level with sum K.
  2. Traverse the given binary tree in a level order fashion.
  3. For each level, check if the sum of the level is equal to K. If yes, then print the level and update flag=true. Else, traverse the next level.
  4. In the end, check if the flag is false. If yes, print “Not Possible” as if there had been at least one level with sum K then the flag would have been true.

Let’s see the code implementation and the time and space complexity analysis in the next section.

C++ Implementation

/*C++ code to print all K-sum levels of the given Binary Tree*/
#include <bits/stdc++.h>
using namespace std;

struct treeNode
    struct treeNode *left;
    int data;
    struct treeNode *right;

void print_K_sum_Levels(treeNode *root, int k)

    if (root == NULL)

    queue<treeNode *> q; // define a queue for level order traversal
    vector<int> level;   // vector to store the elements of the current level

    bool flag = false; // flag to check if k-levelSum exists

    while (!q.empty())

        int cntNodes = q.size();
        int currentLevelSum = 0;

        while (cntNodes > 0)

            treeNode *treeNode = q.front();

            currentLevelSum += treeNode->data;



            if (treeNode->left != NULL)

            if (treeNode->right != NULL)


        if (currentLevelSum == k)
            flag = true;
            // print the level
            for (auto x : level)
                cout << x << " ";
            cout << endl;

        level.clear(); // clear the level vector to store the next level

    if (!flag)
        cout << "Not Possible\n";

treeNode *newNode(int data)
    treeNode *temp = new treeNode;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;

int main()
    treeNode *Root = newNode(10);
    Root->left = newNode(-3);
    Root->right = newNode(7);
    Root->left->left = newNode(5);
    Root->left->right = newNode(-7);
    Root->right->right = newNode(12);
    Root->left->left->left = newNode(-6);

    int K = 10;
    cout << "Levels for K=" << K << endl;
    print_K_sum_Levels(Root, K);

    K = 20;
    cout << "Levels for K=" << K << endl;
    print_K_sum_Levels(Root, K);




Levels for K=10
5 -7 12
Levels for K=20
Not Possible

Complexity Analysis

Time Complexity

The Time Complexity is O(N), where N = the total number of nodes in the binary tree. As we traverse each node of the tree and enqueue and dequeue it from the queue once.

Space Complexity 

The Space Complexity is O(N), where N = the total number of nodes in the binary tree. Since we use a queue to store the nodes of a level, so the space complexity becomes O(N).

Frequently Asked Questions

What is meant by a Binary tree? 

A tree in which every node can have at most two children.

What is the advantage of using Level order traversal?

Level order traversal or Breadth-first search helps you in finding the shortest distance between two nodes.

What is the other name of Level order traversal?

Level order traversal is also known as Breadth-first search as we cover the breadth of the tree first rather than the height.



In this article, we solved the problem to print all the K-Sum levels of a binary tree for a given value of K. We simply used Level Order Traversal to solve this question.
Level Order Traversal is also known as Breadth-First Search, which is very helpful to solve questions related to trees and graphs.

Recommended Problems:

Recommended Reading:


You can check out the course Learn Binary Trees to learn binary trees from scratch.

Are you planning to ace the interviews with reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Previous article
Kth ancestor of a node in a binary tree
Next article
Diamond Tree
Live masterclass