Q:

Find the level in a binary tree with given sum K

mahmoud2506
Save to bookmark
|
2022-04-30
|
  494 
0

Find the level in a binary tree with given sum K

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.

C++ programming, Interview questions, C++ programming Interview-questions,
login and add your own answer to this question

All Answers

mahmoud2506
2022-04-30
need an explanation for this answer? contact us directly to get an explanation for this answer

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

tree image 1

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

Interview C++ coding problems/challenges | tree
This question belongs to these collections

Similar questions

need a help?

find thousands of online teachers now
Check whether a Binary Tree is BST (Binary Search ... >>