Height of Binary Tree

Problem Statement

We are given a binary tree as input and we need to find the height of binary tree. In other words, we are given a binary tree and we need to calculate the maximum depth of the binary tree.

Example

Example : 1

The given binary tree (input) is : $[ 5, 3, 6, 2, 4 ]$.

Tree formed is :

Output :

Example : 2

The given binary tree (input) is : $[ 15, 10, 20, 8, 12, 16, 25, 9 ]$.

Tree formed is :

Output :

Example Explanation

Before getting into the explanation of the example and how to find height of binary tree, let us first get a brief introduction about the binary tree and the height of a binary tree .

A binary tree can be defined as a collection of objects or elements or entities known as nodes. These nodes are linked together to represent a hierarchy.

The top node of the hierarchy is known as the root node. Each node of a binary tree contains some data and it can have at most two child nodes. A root node can never have a parent node. The nodes that do not have any child nodes are termed leaf nodes .

Example :

Now, the height of the binary tree is one more than the largest number of edges in the path from the root node to the lowest level leaf node.

In other words, we can say that the height of binary tree is the height of the root node in the entire binary tree.

In the example :

The root node is $5$ and the lowest level leaf nodes are $2$ and $4$. Now, in the above example, we have the first edge from $5$ to $3$, and the second edge from $3$ to $2$. So, the height of the binary tree comes out to be $3$ [a number of edges + 1].

Constraints

• $1 <=$ Number of nodes $<= 10^5$
• $1 <=$ Data of a node $<= 10^5$

In some problems, you may find the number of test cases represented by t. So, we only need to call the findHeight() function t -times.

Approach : 1

We can easily calculate the height of binary tree using recursion. The idea is very simple, we will calculate the height of the current level, and recursively call the findHeight() function for the left sub-tree and right sub-tree (if they exist).

Now, the height of the current level will be the maximum of the height of the left sub-tree and the height of the right sub-tree .

So, the recursive function will provide the height of the left sub-tree and right sub-tree and we will assign the height of the current node as the maximum of them.

We are recursively left sub-tree and right sub-tree because a node can have a left or a right child or both. Refer to the pseudo-code for a better understanding of the recursive algorithm to find the height of the binary tree.

Algorithm :

The pseudo-code for the same :

1. Check base case :
   • If the tree is empty, return -1 as we cannot find its height.
   • Else, continue the further steps.
2. Call the findHeight(root) function for the left subtree and store the result.
3. Call the findHeight(root) function for the right subtree and store the result.
4. Get the maximum of both the heights and assign the height as the result :
   • height = max(left_height, right_height)
5. Return the result as (height + 1), as we need to add the current node in the total height as well.

Code Implementation

Let us the code implementation of the same in various languages :

C++ Code :

Java Code :

Python Code :

Output :

Time Complexity :

In the recursive approach of finding the height of binary tree, we are traversing all the nodes of the binary tree. So, the time complexity of the algorithm comes out to be $O(n)$, where n is the number of nodes in the binary tree.

Space Complexity :

In the above code, we are not using any extra space but there is recursive calls of the findHeight() function. So, the space complexity comes out to be $O(n)$ as well.

Approach : 2

Another approach to finding the height of the binary tree is to perform the Bread First Search (BFS) or the level order traversal of the binary tree.

We will keep on incrementing the height when we advance to the next level. For performing the level order traversal, we need to use the queue data structure.

The idea is quite simple, we would take a queue and insert the root node into it and initialize a height variable.

Now, we would remove a node from the queue (dequeue) and explore its left and right child, after the exploration, we will increment the height counter by one as each exploration denotes that the current level is done and we should move to the next level.