1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
C++ Implementation
3.2.
Complexity Analysis
4.
4.1.
What is meant by a Binary tree?
4.2.
What is the advantage of using Level order traversal?
4.3.
What is the other name of Level order traversal?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Print all K-sum levels in a Binary Tree

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

## Introduction

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.

Example

1. K=10

The binary tree is given in below figure:

The output will be  -

``````10
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
Bootcamp

## 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:

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

}``````

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

### 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: