Approach
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:
-
Declare a boolean variable flag and initialize flag=false. The flag variable determines whether there is at least one level with sum K.
-
Traverse the given binary tree in a level order fashion.
-
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.
-
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)
return;
queue<treeNode *> q; // define a queue for level order traversal
vector<int> level; // vector to store the elements of the current level
q.push(root);
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;
level.push_back(treeNode->data);
q.pop();
if (treeNode->left != NULL)
q.push(treeNode->left);
if (treeNode->right != NULL)
q.push(treeNode->right);
cntNodes--;
}
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);
}

You can also try this code with Online C++ Compiler
Run Code
Output
Levels for K=10
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.
Conclusion
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!