C++ program to find get level of a node in binary tree using recursion

/**C++ program to find get level of a node in binary tree using recursion**/

/**For calculating level of any node using recursion we need to pass a counter
variable that will count no of level at which recursive function is reach.
At any position of recursive call, if we know that root value is equal to that
searching value then cunter variable will return its value otherwise it will return
0, means searching element is absent in the binary tree.
10
/     \
11      9
/    \   /   \
7   12 18   8

As in this programme we need to check any node only one time.
So that overall time complexity for that programme is O(n)**/

#include<bits/stdc++.h>
#include<queue>

using namespace std;

struct Node
{
int data;
struct Node* left;
struct Node* right;
};

struct Node* newNode(int key)
{
struct Node* temp=new Node;
temp->data=key;
temp->left=temp->right=nullptr;
return temp;
};

/**insert new element in the binary tree;**/

void insert(struct Node* temp, int key)
{
queue<struct Node*> q;
q.push(temp);
while(!q.empty())
{
struct Node* temp=q.front();
q.pop();
if(!temp->left)
{
temp->left=newNode(key);
break;
}
else
q.push(temp->left);

if(!temp->right)
{
temp->right=newNode(key);
break;
}
else
q.push(temp->right);
}
}

/**inorder traversal;**/

void inorder(struct Node* temp)
{
if(temp==nullptr)
return;
else
{
inorder(temp->left);
cout << temp->data << " ";
inorder(temp->right);
}
}

/**calculating level of any node of the binary tree**/

int level(struct Node* temp, int value, int s)
{
int a;
if(temp==nullptr)
return 0;
else
{
if(temp->data==value)
return s;
a=level(temp->left,value,s+1);
if(a!=0)
return a;
a=level(temp->right,value,s+1);
}
return a;
}

int main()
{
int ch,value,s;
struct Node* root=newNode(10);
while(1)
{
cout << "1. insert\n2. inorder\n3. size\nEnter your choise: ";
cin>>ch;
switch(ch)
{
case 1:
cout << "Enter the number: ";
cin>>value;
insert(root,value);
break;
case 2:
cout << "Inorder traversal:" << endl;
inorder(root);
cout << endl;
break;
case 3:
cout << "Enter the number: " << endl;
cin>>value;
s=level(root,value,1);
if(s)
{
cout << "Level of the searching element is:" << endl;
cout << s << endl;
}
else
cout << "Element is absent in the tree" << endl;
break;
default:
cout << "You have entered wrong choise" << endl;
}
}
return 0;
}
/**
Input:
Enter the number:
18
Output:
cout << "Level of the searching element is: " ;
3
**/

More Articles of Ezaz Hossain Sardar:

Name Views Likes
Python Program to Find the first Common Element between the 2 given Linked Lists 254 20
C++ std::valarray_function_name 320 23
C++ std::typeindex_function_name 220 14
C++ std::condition_variable 299 16
C++ mutex mutex_function_name 299 24
C++ std:: 234 20
C++ std::is_trivially_default_constructible 295 20
C++ std::is_trivially_copy_constructible 302 29
C++ std::is_signed 294 25
C++ std::is_scalar 246 15
C++ std::is_same 324 22
C++ std::is_rvalue_reference 269 15
C++ std::is_reference 212 17
C++ std::is_object 257 15
C++ std::is_nothrow_destructible 334 26
C++ std::is_nothrow_constructible 300 22
C++ std::is_member_pointer 240 16
C++ std::is_member_function_pointer 263 19
C++ std::is_literal_type 305 26
C++ std::is_fundamental 262 16
C++ std::is_compound 267 20
C++ std::move for list 297 29
C++ std::move for array 287 22
C++ std::move 273 20
C++ std::replace for array 853 17
C++ std::replace 295 20
C++ std::replace_if 296 22
C++ std::minmax 325 27
C++ std::minmax_element 299 11
C++ std::remove 241 12
C++ std::remove_if 266 18
C++ std::replace_copy 253 20
C++ std::replace_copy_if 234 11
C++ std::remove_copy 272 19
C++ program to find get level of a node in binary tree using recursion 274 28
C++ program to find size of a tree without using recursion 202 14
C++ program to find height of a tree without using recursion 212 17
C++ program to find diameter of a binary tree in O(n) 270 23
C++ program to find diameter of a binary tree 245 13
C++ program to find height of a tree using recursion 215 17
C++ program to count non-leaf nodes in a binary tree using recursion 320 19
C++ program to count leaf nodes in a binary tree using recursion 672 13
C++ program to find sum of all leaf nodes of binary tree 250 21
C++ program to find sum of all the parent nodes having child node x 402 23
C++ program to print path from root to a given node in a binary tree 245 16
C++ program to find distance from root to given node in a binary tree 264 18