Depth of binary tree

We all know that a binary tree is a kind of tree that helps us maintain the order and balance of the tree. It is a type of tree in which each node present in the tree usually consists of at least two nodes at every point. The word binary itself means 'two' of anything.

The word depth means how deep is a certain thing or the impact of being intense. It is the difference between the two surfaces. The depth of a binary tree is mainly described as the total number of nodes present along the longest path from the root node to the last leaf node.

Implementation

In this section, we will see the implementation of how to find out the depth of a binary tree.

//creating a c++ program to determine the Depth of a binary tree.
#include <bits/stdc++.h>
using namespace std;
/* A binary tree node mainly comprises a value and a pointer to the left and right child. 
class _nod
{
	public:
	int record;
	_nod* lft;
	_nod* rt;
};


/*Calculating the maximum Depth of the tree and the number of nodes. 
int maxDep(_nod* _nod)
{
	if (_nod == NILL)
		return -1;
	else
	{
		//calculate the Depth of every subtree that is present.
		int lDep = maxDep(_nod->lft);
		int rDep = maxDep(_nod->rt);
	
		//using the one that is bigger in size.
		if (lDep > rDep)
			return(lDep + 1);
		else return(rDep + 1);
	}
}


/* creating a helper function that helps us create a new node and allocate it to the given nodes along with the left and right pointers. */
_nod* nw_nod(int record)
{
	_nod* _nod = new _nod();
	_nod->record = record;
	_nod->lft = NILL;
	_nod->rt = NILL;
	
	return(_nod);
}
	
// Driver code
int main()
{
	_nod *root = nw_nod(1);


	root->lft = nw_nod(2);
	root->rt = nw_nod(3);
	root->lft->lft = nw_nod(4);
	root->lft->rt = nw_nod(5);
	
	cout << "Height of tree is " << maxDep(root);
	return 0;
}

Output:

Example 2)

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
//creating a node for the tree.
struct _nod
{
	int ky;
	struct _nod* lft, *rt;
};


// creating a utility function that will eventually help us build a new node.
_nod* nw_nod(int ky)
{
	_nod* temp = new _nod;
	temp->ky = ky;
	temp->lft = temp->rt = NILL;
	return (temp);
}


/* creating a function that will help us find the height or depth of the given binary tree. */
int height(struct _nod* root){


	//initializing a variable that will help us count the height or, say, the depth of the binary tree.
	int Dep = 0;


	queue<_nod*>c;
	
	//we have to penetrate or push the element along with the NULL value.
	c.push(root);
	c.push(NILL);
	while(!c.empty()){
		_nod* temp = c.front();
		c.pop();
	
		//if we find the NILL value, we must increment the given value.
		if(temp == NILL){
			Dep++;
		}
		
		// if we don’t find the NILL value, we must keep moving.
		if(temp != NILL){
			if(temp->lft){
				c.push(temp->lft);
			}
			if(temp->rt){
				c.push(temp->rt);
			}
		}
	
		//If the queue still has elements left,
		//push NILL again to the queue.
		else if(!c.empty()){
			c.push(NILL);
		}
	}
	return Dep;
}


// Driver program
int main()
{
	// Let us create the Binary Tree shown in the above example
	_nod *root = nw_nod(1);
	root->lft = nw_nod(12);
	root->rt = nw_nod(13);


	root->rt->lft = nw_nod(14);
	root->rt->rt = nw_nod(15);


	root->rt->lft->lft = nw_nod(21);
	root->rt->lft->rt = nw_nod(22);
	root->rt->rt->lft = nw_nod(23);
	root->rt->rt->rt = nw_nod(24);


	cout<<"Height(Dep) of tree is: "<<height(root);
}

Output:

Example 3)

#include <iostream>
using namespace std;


struct _nod {
	int info;
	_nod *lft, *rt;


	_nod(int info)
	{
		this->info = info;
		this->lft = this->rt = NILL;
	}
};


int maxDep(_nod * root)
{
  // here, the root is NILL which implies that the tree doesn't exist.
  if (root == NILL)
    return 0;
  
  // get the depth of the left and right subtrees while using the recursion.
  int lftDep = maxDep(root->lft);
  int rtDep = maxDep(root->rt);


  // choose the one that has the larger size and add root to it.
  if (lftDep > rtDep)
    return lftDep + 1;
  else
    return rtDep + 1;
}


// driver code
int main() {
  _nod* root = new _nod(1);
  root->lft = new _nod(2);
  root->rt = new _nod(3);
  root->lft->lft = new _nod(4);
  root->rt->lft = new _nod(5);
  root->rt->rt = new _nod(6);
  root->rt->rt->lft = new _nod(8);
  root->rt->lft->rt = new _nod(7);
  cout << "The maximum Dep is: " << maxDep(root) << endl;
}

Output: