Level of a given node in binary tree

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
       /   \
     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.

Start at the Root with level=0
If ptr == root pointer
return level
Call the function recursively for left subtree and right subtree

/* 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);

    return 0;

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation