Home » Interview coding problems/challenges

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