Level of a node in the given 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

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;
    }

We may also visualize the solution differently. If we are not passing the current level to the function, then we can think of the function returning the level of Node in the Current Tree (whose root is at r, It may be different from the main tree).

If the node is present at level x in the left subtree, the the level of node in the main tree will be x+1.

We are using this approach below.

/**
   * Return level of ptr in the Tree whose root is r
   * @param r - Root of the Current Tree
   * @param ptr - Pointer to the Node we want to search
   * @return -1 if Node is not present in the current Tree
   *          x if Node is present at level x in the Current Tree
   */
  int findLevel(Node r, Node ptr)
  {
    if(r == null || ptr == null){ return -1; }
    if(r.data == ptr.data){
      // ptr found at level 0 in the Current Tree 
      // (It may not be level-0 in the main tree)
      return 0; 
    }

    // Search Level of ptr in Left SubTree
    int a = findLevel(r.left, ptr);

    if(a != -1) // Found in Left SubTree at level a
      return a+1; 
    
    // Search Level of ptr in Left SubTree
    a = findLevel(r.left, ptr);

    if(1 != -1)
      return a+1;
    else  
      return -1; // NOT FOUND
  }

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: This is a relatively simple code using level-Order Traversal of the Binary Tree