Jul 312012
 

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

In the Tree on left side:

Root Node (Node with value 10) is at level-0
Nodes with values 5 and 30 are at level-1
Nodes with values 4, 8 and 40 are at level-2
Node with value 1 is at level-3

Signature of the function is:

    /** Function returns the level of Node pointed to by ptr, in the Binary Tree
     *  pointed to by root.
     *
     *  If the Tree is NULL or the Node is not present in the tree, 
     *  then it returns -1 (Invalid level).
     */
    int findLevel(Node* root, Node* ptr)


Structure of the Node is:

    struct Node
    {
        int data;
        Node *lptr;
        Node *rptr;
    };

Method-1 (Using Recursion):

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

Code:

    /** Function returns the level of Node pointed to by ptr, in the Binary Tree
     *  pointed to by root.
     *
     *  If the Tree is NULL or the Node is not present in the tree, 
     *  then it returns -1 (Invalid level).
     */
    int findLevel(Node* root, Node* ptr, int level=0)
    {
        if(root == NULL)
            return -1;

        if(root == ptr)
            return level;

        // If NULL or leaf Node
        if(root->lptr == NULL && root->rptr == NULL)
            return -1;

        // Find If ptr is present in the left or right subtree.
        int levelLeft = findLevel(root->lptr, ptr, level+1);
        int levelRight = findLevel(root->rptr, ptr, level+1);

        if(levelLeft == -1)
            return levelRight;
        else
            return levelLeft;
    }

Method-2: Using BFS

In this case we use the BFS (Breadth First Search Algorithm) which is the same algorithm we used to traverse the tree in level wise order.

Traverse the tree in level-wise order 
Keep a track of the level of the node.
when a Node equal to ptr is encountered, return the level.
If the tree is exhausted and the Node is not found return -1

Code:

<Will Update in 1 day, tomorrow>
Please let me know your comments.

  2 Responses to “Level of node in a Binary Tree”

Comments (2)
  1. In the findlevel function, we can check if the value of the ptr is than value of root ptr and accordingly we can traverse left or right tree and not both as its being done in this function.

    Also its not very easy to write comments in this website as home/end keys are disabled and the mouse clicks are also disabled in the comment section.

 Leave a Reply

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=""> <s> <strike> <strong>

(required)

(required)