Level of a Node in a Binary Tree in C++

In this tutorial, we will learn about how to find the level of the node in a binary tree. We will also see the code implementation in c++.

We will also see examples to understand the concept in a better way.

Level of Node in a Binary tree

The level of a node is a depth of a node in a binary tree. Level of the root node is 1.

Let,s see the example,

                          1
                        /   \
                       2     6
                       \    / \
                        3  7   9    level of 7 is 3.
                       / \ \ 
                      4   5 8 

                          1 
                        /   \ 
                       2     3      level of 5 is 3. 
                      / \   / \ 
                     4   5 6   7

So, we can see the level of node in the above examples.

Firstly we discuss the recursive approach.

Recursive Approach

Let,s see the approach,

  • Start with the root of level 1. If the root data is equal to key data then return level.
  • Recursively call the left subtree with level is level+1.
  • Recursively call the right subtree with level is level+1.

Code implementation in c++

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//structure of Node
struct Node{
  int data;
  Node* left;
  Node* right;
};
//function to create the node
Node* create(int x){
  Node* temp=new Node;
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//function to find the level of node
int find(Node* root,int t,int l)
{
    if(!root)return 0;
    if(root->data==t)return l;
    int x=find(root->left,t,l+1);
    if(x!=0)return x;
    x=find(root->right,t,l+1);
    return x;
}
int getLevel(struct Node *node, int target)
{
    if(!node)return 0;
  int l=1;
    return find(node,target,l);
}
//main fuction
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(5);
  root->left->left=create(4);
  root->right=create(3);
  root->right->left=create(6);
  root->right->right=create(7);
    cout<<"level of 5 is :"<<" ";
    cout<<getLevel(root,5);
    return 0;
}

Output

level of 5 is : 3

Let’s see the level order traversal approach.

Level order traversal approach

We will simply use the level order traversal to find the level of node.

Code implementation in c++

Below is the given code snippet:

#include<iostream>
#include<bits/stdc++.h>
using namespace std;
//structure of Node
struct Node{
  int data;
  Node* left;
  Node* right;
};
//function to create the node
Node* create(int x){
  Node* temp=new Node;
  temp->data=x;
  temp->left=NULL;
  temp->right=NULL;
  return temp;
}
//function to find the level of node
int getLevel(struct Node *node, int target)
{   queue<Node*>q;
q.push(node);
q.push(NULL);
int level=1;
    while(!q.empty()){
        Node* temp=q.front();
        q.pop();
        if(temp==NULL){
            q.push(NULL);
            level++;
            if(q.front()==NULL)return 0;
            continue;
        }
        if(temp->data==target)return level;
        if(temp->left!=NULL)q.push(temp->left);
        if(temp->right!=NULL)q.push(temp->right);
    }
}
//main fuction
int main(){
  Node* root=create(1);
  root->left=create(2);
  root->left->right=create(5);
  root->left->left=create(4);
  root->right=create(3);
  root->right->left=create(6);
  root->right->right=create(7);
    cout<<"level of 5 is :"<<" ";
    cout<<getLevel(root,5);
    return 0;
}

Output

level of 5 is : 3

You may also learn,

How to find lowest common ancestor in binary tree in Java

Right view of the binary tree in C++

Leave a Reply

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