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,
Leave a Reply