# Find the level in a binary tree with given sum K

Here, we are going to learn how to find the level in a binary tree with given sum K – its an interview coding problem came in Samsung, Microsoft?
Submitted by Radib Kar, on November 25, 2018

Description:

The article describes how to find the level in a binary tree with given sum K? This is an interview coding problem came in Samsung, Microsoft.

Problem statement:

Given a binary tree and an integer K, output the level no of the tree which sums to K. Assume root level is level 0.

Solution

Algorithm:

One of the popular traversal techniques to solve this kind of problems is level order tree traversal (Read more: Level Order Traversal on a Binary Tree) where we use the concept of BFS with some modifications.

1. Set a variable level=0 & declare a variable of type tree* named temp. level is a flag for the current level & temp stores tree node to be processed.

2. Set cur_sum=0

3. if(!root) // root is NULL
return -1; //no such level exists

4. q=createQueue() //to store pointers to tree node

5. EnQueue(q,root);

6. EnQueue(q,NULL);

Every time, we EnQueue a NULL to reflect the end of current level. Same way while processing when NULL is found, it reveals that end of current level.

```7. while( q is not empty)
temp=DeQueue(q);
if(temp==NULL){ //end of current level
if (cur_sum==K) // current level sum is equal to K
Return level; //return level no (root is at 0 level)
else {
Set cur_sum =0; // for next level
If(q is not empty)
// to reflect end of next level which
// will be processed in next iteration
EnQueue(q,NULL)
Increase level //increase level count
}
}
Else{
cur_sum+=temp->data; //sum the level
//do level order traversal
If(temp->left)
EnQueue(temp->left);
If(temp->right)
EnQueue (temp->right);
}
End while loop
```

8. If program control comes out of while loop then surely no level has a sum K. Thus print no level has sum K

Example:

```Here the level sums are:
For level 0: 2
For level 1: 12
For level 2: 17
For level 3: 20
Thus if K is 12 our program will print level 1
```

## C++ code to find the level in a binary tree with given sum K

```#include <bits/stdc++.h>
using namespace std;

// tree node is defined
class tree{
public:
int data;
tree *left;
tree *right;
};

int findLevel( tree *root,int K){
queue<tree*> q;  // using stl
tree* temp;
//counting level no & initializing cur_sum
int level=0,cur_sum=0;
//EnQueue root
q.push(root);
//EnQueue NULL to inticate end of 0 level
q.push(NULL);
while(!q.empty()){
//DeQueueing using STL
temp=q.front();
q.pop();
if(temp==NULL){
//if current level sum equals to K
if(cur_sum==K)
return level;//return level no
//ifn't then set cur_sum to 0 for further levels
cur_sum=0;
if(!q.empty())
q.push(NULL);
level++;
}
else{
//level order traversal
cur_sum+=temp->data; //sum thd level
if(temp->left)
q.push(temp->left); //EnQueue
if(temp->right)
q.push(temp->right); //EnQueue
}
}
return -1;
}

// creating new node
tree* newnode(int data)
{
tree* node = (tree*)malloc(sizeof(tree));
node->data = data;
node->left = NULL;
node->right = NULL;

return(node);
}

int main()
{
//**same tree is builted as shown in example**
int c,K;
cout<<"Tree is built like the example aforesaid"<<endl;
cout<<"input K....."<<endl;
cin>>K;

tree *root=newnode(2);
root->left= newnode(7);
root->right= newnode(5);
root->right->right=newnode(9);
root->right->right->left=newnode(4);
root->left->left=newnode(2);
root->left->right=newnode(6);
root->left->right->left=newnode(5);
root->left->right->right=newnode(11);

cout<<"finding if any level exists......"<<endl;
c=findLevel(root,K);
if(c>=0)
cout<<"level is found and it is level "<<c<<endl;
else
cout<<"level not found, no such tree level exists";

return 0;
}
```

Output

```First run:
Tree is built like the example aforesaid
input K.....
20
finding if any level exists......
level is found and it is level 3

Second run:
Tree is built like the example aforesaid
input K.....
25
finding if any level exists......
level not found, no such tree level exists
```

What's New (MCQs)

Top Interview Coding Problems/Challenges!

IncludeHelp's Blogs

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.