Print all K-sum levels in a Binary Tree

Yukti Kumari
Last Updated: May 13, 2022

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.

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

 

Time Complexity

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 

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

  1. What is meant by a Binary tree? 
    A tree in which every node can have at most two children.
     
  2. 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.
     
  3. 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 height.

 

Key Takeaways

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 the questions related to trees and graphs.

Try practising this problem - Perform Level Order Traversal on Codestudio.

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

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

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think