Level of a Given Node

By | October 27, 2015

Finding Level of a Given Node in a Binary Tree.

Given a Binary Tree, we need to print the level of a given data/node in the Binary Tree, or print a statement to tell it is absent from the tree in case it is not present.

Level of a Given Node in a Binary Tree Example:

             80                 
           /     \        
          60      110     
         /  \    /       
       35   40  85   
      /  \
     64   72

For the tree shown above, the output should be

for 80 : the level is 1
for 72 : the level is  4   and so on…
88 not found in the Tree.

Finding Level of a Given Node in a Binary Tree Solution:

Here we sent level and  the key to be searched as the parameter to a function.

Algorithm:

  1. If the root is NULL, then return 0.
  2. If  the key matches the root’s data, then return the level,
  3. Else Recur on Left Subtree with level+1,
  4. If still the node is not found, recur on Right subtree, with level+1.

Level of a Given Node in a Binary Tree Solution code:

Here is the working code:

#include <bits/stdc++.h>
using namespace std;

/*Structure for each node of the tree*/
struct node
{
   int data;
   node *right,*left;
};


/*Function that allocates memory for
each new node and initialises it*/
node * newNode(int data)
{
   node *temp=new node;
   temp->data=data;
   temp->left=NULL;
   temp->right=NULL;
   
   return temp;
}

/*This function returns the level of a given node
in a Binary Tree, if not present, it returns 0*/
int LevelOfaNode(node *root,int level,int key)
{
   if(!root)
      return 0;
   /*returns level if Key matches the data*/	
   if(key == root->data)	
      return level;
   
   /*We check in the left Subtree*/	
   int inLeftSubTree = LevelOfaNode(root->left,level+1,key);
   if(inLeftSubTree)
      return inLeftSubTree;
   
   /*If the value, is not present in Left Subtree
   we Recur on right subtree*/	
   return LevelOfaNode(root->right,level+1,key);
   
   /*Note that every Time we Recur, we 
   increment the level by 1*/
}


int main()
{
  /*        
  We are making the following tree
  	          80                 
            /    \        
          60      110     
         /  \    /       
       35   40  85 
      /  \
     64  72
   */
  node *root               = newNode(80);
  root->left               = newNode(60);
  root->right              = newNode(110);
  root->left->left         = newNode(35);
  root->left->right        = newNode(40);   
  root->right->left 	   = newNode(85);  
  root->left->left->left   = newNode(64);
  root->left->left->right  = newNode(72);
  
  /*Here we store the above elements in an array
  so that they can be searched easily.
  Also, we add 88, which is not present in the 
  Tree to test for absent */
  int arr[]={80, 60, 110, 35, 88, 40, 85, 64, 72};
  int size= sizeof(arr)/sizeof(arr[0]);
  for(int i=0; i<size ;++i)
  {
  	  int level=LevelOfaNode(root,1,arr[i]);
  	  if(level)
  	  {
  	  	  /*If the Key/data  is found*/
  	  	  cout<<"The level of "<<arr[i]<<" is : ";
  	  	  cout<<level<<"\n";
  	  }	  
  	  else
  	  	  cout<<arr[i]<<" is Not Present in the Tree\n";
  }
  return 0;
}

Output:

The level of 80 is : 1
The level of 60 is : 2
The level of 110 is : 2
The level of 35 is : 3
88 is Not Present in the Tree
The level of 40 is : 3
The level of 85 is : 3
The level of 64 is : 4
The level of 72 is : 4

Time Complexity: O(N) worst case all nodes are traversed.