Given a Binary Tree and a pointer to the Node in that tree. Write a function to find level of Node in the Tree. For Example, in the below tree
0
/ \
1 4
/ \ / \
2 3 5 6
If the input key is 3, then your function should return 3. If the input key is 4, then your function should return 2 and for key which is not present in key, then your function should return 0.
Steps:
Start at the Root with level=0
If ptr == root pointer
return level
Else
Call the function recursively for left subtree and right subtree
#include<stdio.h>
/* A tree node structure */
struct node
{
int data;
struct node *left;
struct node *right;
};
int getLevel(struct node* root, int n, int level)
{
if(root == NULL)
return 0;
if(root->data == n)
return level;
return getLevel(root->left, n, level+1) |
getLevel(root->right, n, level+1);
}
/* 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 = new struct node;
int x;
/* Constructing tree given in the above figure */
root = newNode(0);
root->left = newNode(1);
root->right = newNode(4);
root->left->left = newNode(2);
root->left->right = newNode(3);
root->right->left = newNode(5);
root->right->right = newNode(6);
int level = getLevel(root, 5, 1);
printf("%d",level);
return 0;
}
Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.
