Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
3.1.
C++ Implementation
3.2.
Complexity Analysis
4.
Frequently Asked Questions
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

Author Yukti Kumari
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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:

 

illustration image

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.

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


}
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!

Live masterclass