Height of a binary tree

The height of a binary tree is generally defined as the height or length of the root _nod in the entire binary tree. In simple words, the height of a binary tree is generally the maximum distance we acquire from the root _nod to the far fetch leaf _nod in the entire binary tree. Finding out the binary tree's height is very similar to finding out the depth of the binary tree. In this article, we are mainly going to see the implementation of how to find the height of the binary tree.

Implementation

In this section, we will see the implementation of the binary Trees while using arrays. let us proceed: -

#include <bits/stdc++.h>
using namespace std;
// A typical binary contains the value of the node along with the left and right pointers.
class _nod
{
	public:
	int record;
	_nod* lft;
	_nod* rt;
};


/* Compute the "maxDepth" of a tree -- the number of
	_nods along the longest path from the root _nod
	down to the farthest leaf _nod.*/
int maxDepth(_nod* _nod)
{
	if (_nod == NILL)
		return -1;
	else
	{
		/* compute the depth of each subtree */
		int lDepth = maxDepth(_nod->lft);
		int rDepth = maxDepth(_nod->rt);
	
		/* use the larger one */
		if (lDepth > rDepth)
			return(lDepth + 1);
		else return(rDepth + 1);
	}
}


/* Helper function allocates a new _nod with the
given record, NILL lft, and rt pointers. */
_nod* new_nod(int record)
{
	_nod* _nod = new _nod();
	_nod->record = record;
	_nod->lft = NILL;
	_nod->rt = NILL;
	
	return(_nod);
}
	
// 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->lft->rt = new_nod(5);
	
	cout << "Height of tree is " << maxDepth(root);
	return 0;
}

Output:

Example 2)

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


// A Tree _nod
struct _nod
{
	int key;
	struct _nod* lft, *rt;
};


// Utility function to create a new _nod
_nod* new_nod(int key)
{
	_nod* temp = new _nod;
	temp->key = key;
	temp->lft = temp->rt = NILL;
	return (temp);
}


/*Function to find the height(depth) of the tree*/
int height(struct _nod* root){


	//Initialising a variable to count the
	//height of the tree
	int depth = 0;


	queue<_nod*>q;
	
	//Pushing first-level element along with NILL
	q.push(root);
	q.push(NILL);
	while(!q.empty()){
		_nod* temp = q.front();
		q.pop();
	
		//When NILL is encountered, increment the value
		if(temp == NILL){
			depth++;
		}
		
		//If NILL not encountered, keep moving
		if(temp != NILL){
			if(temp->lft){
				q.push(temp->lft);
			}
			if(temp->rt){
				q.push(temp->rt);
			}
		}
	
		//If the queue still has elements left,
		//push NILL again to the queue.
		else if(!q.empty()){
			q.push(NILL);
		}
	}
	return depth;
}


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


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


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


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

Output:

Example 3)

#include <iostream>
#include <list>
using namespace std;
 
// Record structure to store a binary tree _nod
struct _nod
{
    int key;
    _nod *lft, *rt;
 
    _nod(int key)
    {
        this->key = key;
        this->lft = this->rt = NILLptr;
    }
};
 
// Iterative function to calculate the height of a given binary tree
// by doing level order traversal on the tree
int height(_nod* root)
{
    // empty tree has a height of 0
    if (root == NILLptr) {
        return 0;
    }
 
    // create an empty queue and enqueue the root _nod
    list<_nod*> queue;
    queue.push_back(root);
 
    _nod* front = NILLptr;
    int height = 0;
 
    // loop till queue is empty
    while (!queue.empty())
    {
        // calculate the total number of _nods at the current level
        int size = queue.size();
 
        // process each _nod of the current level and enqueue their
        // non-empty left and right child
        while (size--)
        {
            front = queue.front();
            queue.pop_front();
 
            if (front->lft) {
                queue.push_back(front->lft);
            }
 
            if (front->rt) {
                queue.push_back(front->rt);
            }
        }
 
        // increment height by 1 for each level
        height++;
    }
 
    return height;
}
 
int main()
{
    _nod* root = new _nod(15);
    root->lft = new _nod(10);
    root->rt = new _nod(20);
    root->lft->lft = new _nod(8);
    root->lft->rt = new _nod(12);
    root->rt->lft = new _nod(16);
    root->rt->rt = new _nod(25);
 
    cout << "The height of the binary tree is " << height(root);
 
    return 0;
}

Output: