#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
using namespace std;
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
/* Returns level of given data value */
int getLevel(struct node *root, int data)
{
std::queue<struct node*> q;
q.push(root);
int level = 1;
while(!q.empty()){
q.push(NULL);
while(q.front() != NULL){
struct node *temp = q.front();
q.pop();
if(temp->data == data){
return level;
}
if(temp->left){
q.push(temp->left);
}
if(temp->right){
q.push(temp->right);
}
}
q.pop();
level = level+1;
}
return 0;
}
/* Utility function to create a new Binary Tree node */
struct node* newNode(int data)
{
struct node *temp = new struct node;
temp->data = data;
temp->left = NULL;
temp->right = NULL;
return temp;
}
/* Driver function to test above functions */
int main()
{
struct node *root = (struct node*)malloc(sizeof(struct node));
int x;
/* Constructing tree given in the above figure */
root = newNode(3);
root->left = newNode(2);
root->right = newNode(5);
root->left->left = newNode(1);
root->left->right = newNode(4);
/* for (x = 1; x <=5; x++)
{*/
x= 7;
int level = getLevel(root, x);
if (level)
printf(" Level of %d is %d\n", x, getLevel(root, x));
else
printf(" %d is not present in tree \n", x);
// }
getchar();
return 0;
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPGNzdGRsaWI+CiNpbmNsdWRlPGNzdGRpbz4KI2luY2x1ZGU8cXVldWU+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Ci8qIEEgdHJlZSBub2RlIHN0cnVjdHVyZSAqLwpzdHJ1Y3Qgbm9kZQp7CglpbnQgZGF0YTsKCXN0cnVjdCBub2RlICpsZWZ0OwoJc3RydWN0IG5vZGUgKnJpZ2h0Owp9OwoKLyogUmV0dXJucyBsZXZlbCBvZiBnaXZlbiBkYXRhIHZhbHVlICovCmludCBnZXRMZXZlbChzdHJ1Y3Qgbm9kZSAqcm9vdCwgaW50IGRhdGEpCnsKICAgIHN0ZDo6cXVldWU8c3RydWN0IG5vZGUqPiBxOwogICAgcS5wdXNoKHJvb3QpOwogICAgaW50IGxldmVsID0gMTsKICAgIHdoaWxlKCFxLmVtcHR5KCkpewogICAgICAgIHEucHVzaChOVUxMKTsKICAgICAgICB3aGlsZShxLmZyb250KCkgIT0gTlVMTCl7CiAgICAgICAgICAgIHN0cnVjdCBub2RlICp0ZW1wID0gcS5mcm9udCgpOwogICAgICAgICAgICBxLnBvcCgpOwogICAgICAgICAgICBpZih0ZW1wLT5kYXRhID09IGRhdGEpewogICAgICAgICAgICAgICAgcmV0dXJuIGxldmVsOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHRlbXAtPmxlZnQpewogICAgICAgICAgICAgICAgcS5wdXNoKHRlbXAtPmxlZnQpOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGlmKHRlbXAtPnJpZ2h0KXsKICAgICAgICAgICAgICAgIHEucHVzaCh0ZW1wLT5yaWdodCk7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgcS5wb3AoKTsKICAgICAgICBsZXZlbCA9IGxldmVsKzE7CiAgICB9CiAgICByZXR1cm4gMDsKfQoKLyogVXRpbGl0eSBmdW5jdGlvbiB0byBjcmVhdGUgYSBuZXcgQmluYXJ5IFRyZWUgbm9kZSAqLwpzdHJ1Y3Qgbm9kZSogbmV3Tm9kZShpbnQgZGF0YSkKewoJc3RydWN0IG5vZGUgKnRlbXAgPSBuZXcgc3RydWN0IG5vZGU7Cgl0ZW1wLT5kYXRhID0gZGF0YTsKCXRlbXAtPmxlZnQgPSBOVUxMOwoJdGVtcC0+cmlnaHQgPSBOVUxMOwoKCXJldHVybiB0ZW1wOwp9CgovKiBEcml2ZXIgZnVuY3Rpb24gdG8gdGVzdCBhYm92ZSBmdW5jdGlvbnMgKi8KaW50IG1haW4oKQp7CglzdHJ1Y3Qgbm9kZSAqcm9vdCA9IChzdHJ1Y3Qgbm9kZSopbWFsbG9jKHNpemVvZihzdHJ1Y3Qgbm9kZSkpOwoJaW50IHg7CgoJLyogQ29uc3RydWN0aW5nIHRyZWUgZ2l2ZW4gaW4gdGhlIGFib3ZlIGZpZ3VyZSAqLwoJcm9vdCA9IG5ld05vZGUoMyk7Cglyb290LT5sZWZ0ID0gbmV3Tm9kZSgyKTsKCXJvb3QtPnJpZ2h0ID0gbmV3Tm9kZSg1KTsKCXJvb3QtPmxlZnQtPmxlZnQgPSBuZXdOb2RlKDEpOwoJcm9vdC0+bGVmdC0+cmlnaHQgPSBuZXdOb2RlKDQpOwoKLyoJZm9yICh4ID0gMTsgeCA8PTU7IHgrKykKCXsqLwoJeD0gNzsKCWludCBsZXZlbCA9IGdldExldmVsKHJvb3QsIHgpOwoJaWYgKGxldmVsKQoJCXByaW50ZigiIExldmVsIG9mICVkIGlzICVkXG4iLCB4LCBnZXRMZXZlbChyb290LCB4KSk7CgllbHNlCgkJcHJpbnRmKCIgJWQgaXMgbm90IHByZXNlbnQgaW4gdHJlZSBcbiIsIHgpOwoKLy8JfQoKCWdldGNoYXIoKTsKCXJldHVybiAwOwp9Cg==