1. Overview

In this tutorial, we’ll discuss how to find the height of a binary tree with an example.

2. Definition

Let’s first start with a definition of the height of a binary tree.

The height of a node in a binary tree is the largest number of edges in a path from a leaf node to a target node. If the target node doesn’t have any other nodes connected to it, the height of that node would be \mathsf{0}. The height of a binary tree is the height of the root node in the whole binary tree. In other words, the height of a binary tree is equal to the largest number of the edges from the root to the most distant leaf node.

A similar concept in a binary tree is the depth of the tree. The depth of a node in a binary tree is the total number of edges from the root node to the target node. Similarly, the depth of a binary tree is the total number of edges from the root node to the most distant leaf node.

One important observation here is that when we calculate the depth of a whole binary tree, it is equivalent to the height of the binary tree.

3. Example

Let’s take a binary tree:

Firstly, we’re calculating the height of the node C. So, according to the definition, the height of the node C is the largest number of edges in a path from the leaf node to the node C. We can see for the node C, there are two paths: C \rightarrow E \rightarrow G and C \rightarrow F. The largest number of edges among these two paths would be \mathsf{2}. Hence the height of node C is \mathsf{2}.

Now, let’s calculate the height of the binary tree. From the root, we can have three different paths leading to the leaf nodes: A \rightarrow C \rightarrow F, A \rightarrow B \rightarrow D, and A \rightarrow C \rightarrow E \rightarrow G. Among these three paths, the path A \rightarrow C \rightarrow E \rightarrow G contains the most number of edges that is \mathsf{3}. Therefore the height of the tree is \mathbf{3}.

Next, we want to find the depth of the node B. Now we can see that from the root, there is only one path to the node B, and it has one edge. Hence the depth of the node B is \mathsf{1}. The depth of a binary tree is equal to the height of the tree. Therefore, the depth of the binary tree is \mathbf{3}.

4. Algorithm

Now we know the definition of the height of a binary tree. Let’s see an algorithm to find the height of a binary tree:

Rendered by QuickLaTeX.com

We start the algorithm by taking the root node as an input. Next, we calculate the height of the left and right child nodes of the root. In case the root doesn’t have any child node, we return the height of the tree as \mathsf{0}.

We recursively call all the nodes from the left and right subtree of the root node to calculate the height of a binary tree. Finally, when we calculate the height of the left and right subtree, we take the maximum height among both and add one to it. The number return by the algorithm would be the height of the binary tree.

5. Time Complexity Analysis

In the best case, we can have only one node in the binary tree. In such a case, we only execute the first condition of the algorithm when the root is null and return the height of the tree as \mathsf{0}. Here, the time complexity would be \mathbf{\mathcal{O}(1)}.

In general, we calculate the height of each node in the tree. We call all the nodes recursively, calculate the height of the left and right subtree from the root node, and finally return the height of the whole binary tree. Hence, we visit all the nodes in the tree.

Let’s consider the number of nodes in a binary tree is n. Therefore, the time complexity would be \mathbf{\mathcal{O}(n)}.

6. Conclusion

In this tutorial, we discussed how to calculate the height of a binary tree. We presented a recursive algorithm and analysis of the time complexity required for the algorithm.

guest
0 Comments
Inline Feedbacks
View all comments