What’s New ?

The Top 10 favtutor Features You Might Have Overlooked

Read More

Height of a Binary Tree (Python Code with example)

  • May 08, 2021
  • 7 Minutes Read
Height of a Binary Tree (Python Code with example)

 

A binary tree is a unique data structure adopted for data storage schemes in the field of computer science. Each node in a binary tree can have at most two children. Using a binary tree data structure is beneficial because it has the benefits of both an ordered array and a linked list, therefore, the time complexity for search is as fast as in a sorted array, and insertion or deletion operations are as swift as in a linked list. Example of a binary tree: 

Binary Tree Example

How to find the Height of a binary tree?

The height of the binary tree is considered to be the longest path starting from the root node to any leaf node in the binary tree. If the target node for which we have to calculate height for, doesn’t have any other nodes connected to it, conclusively the height of that node would be 0. Therefore, we can say that the height of a binary tree is the elevation from the root node in the entire binary tree. In layman's terms, the height of a binary tree is equivalent to the largest quantity of the edges starting from the root to the most sparse leaf node in the binary tree.

A related concept in binary tree data structure is the depth of the tree. According to the definition of depth of a node in the binary tree is the total amount of edges starting from the root node to the destination node. Furthermore, the depth of a binary tree is the total amount of edges starting from the root node to the most far-flung leaf node. And in this article, we will learn how to find the height/max depth of a binary tree using recursion and without using recursion. 

Example

The figure below shows a binary tree with 4 levels indicated. 

find height of a binary tree

 

The leaf nodes of the binary tree are : [70, 80, 50, 90] 

For the leaf node 70, the number of nodes along the edges is 4. 

For the leaf node 80, the number of nodes along the edges is 4. 

For the leaf node 50, the number of nodes along the edges is 3. 

For the leaf node 90, the number of nodes along the edges is 4.

The maximum number of node from root to farthest leaf is: max(4, 4, 3, 4) is 4. Hence, height of the binary tree is 4. 

Algorithm for Calculating Height of a Binary Tree

There are two methods to approach this problem statement. First Approach is based on Depth first seach using recursion, and the other method is based on Breadth first search using Level order traversal without using recursion. 

 

Finding The Height With Recursion (Depth First search approach)

Let us consider an example to understand the approach in an easier way. Consider the following Binary Tree, with ‘a’ as the root node and ‘h’, ‘e’, ‘f’ and ‘g’ as the leaf node: 

Depth first search approach

For the leaf node ‘h’, the number of nodes along the edges is 4. 

For the leaf node ‘e’, the number of nodes along the edges is 3. 

For the leaf node ‘f’, the number of nodes along the edges is 3. 

For the leaf node ‘g’, the number of nodes along the edges is 3.

 

The maximum number of node from root to farthest leaf is: max(4, 3, 3, 3) is 4. Hence, height of the binary tree is 4. 

Let us discuss the step-by-step implementation 

Step 1: Ask the root node, what is the height of the binary tree if the root node is ‘a’, and recursively the root node asks the same question to its left which is ‘b’ and right child which is ‘c’. And so on.  

 

Checking the root node

 

Step 2: Recursively ‘b’ will do the same as the node ‘a’ and ask its left child ‘d’ and the right child ‘e’ what will be the height if you are the root node of the current binary tree, ie. 

Applying recursion on node a

Step 3: The node ‘d’ asks the same questions to it’s left and right child ie. 

Applying recursion on Node d

The node ‘h’ does the same thing and now since the left node of ‘h’ is NULL it returns 0. 

Step 4: The node ‘h’ gives out the result of its left and right child, and after we find the maximum length between the leftHeight and rightHeight, where : 

leftHeight = 0 

rightHeight = 0

Node h showing the result of its left and right child

 

max(0, 0) = 0 

Therefore, at each iteration the node will return length: 1 + max(leftHeight, rightHeight)

Step 5: To get a better intuition of the algorithm, refer to the following image:

 

Depth first search algorithm in order to find height of a binary tree

 

 Python Code (with Recursion): 

# define a Class Tree, to intiate the binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def height(root):
 
    # Check if the binary tree is empty
    if root is None:
        # If TRUE return 0
        return 0 
    # Recursively call height of each node
    leftAns = height(root.left)
    rightAns = height(root.right)
 
    # Return max(leftHeight, rightHeight) at each iteration
    return max(leftAns, rightAns) + 1
 
# Test the algorithm
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
 
print("Height of the binary tree is: " + str(height(root)))

 

Output: Height of a simple binary tree:

Height of a binary tree output

 

Height of the binary tree is: 3

 

Time and Space Complexity:

The time complexity of the algorithm is O(n) as we iterate through node of the binary tree calculating the height of the binary tree only once.

And the space complexity is also O(n) as we are following recursion, where recursive stack can have upto n elements. 

Where n is the number of nodes in the binary tree.

 

Finding the Height Without Recursion (Breadth-First search approach)

Let us consider an example to understand the approach in a easier way. Consider the following Binary Tree, with 12 as the root node and 19, 16, 7 and 8 as the leaf node: 

 

Breadth first search approach example

For the leaf node 19, the number of nodes along the edges is 4. 

For the leaf node 16, the number of nodes along the edges is 3. 

For the leaf node 7, the number of nodes along the edges is 3. 

For the leaf node 8, the number of nodes along the edges is 3.

 

The maximum number of node from root to farthest leaf is: max(4, 3, 3, 3) is 4. Hence, height of the binary tree is 4.  

Let us discuss the step-by-step implementation 

 

Step 1: Use a queue data structure to approach this problem statement, hence, initialize an empty queue data structure.  

Initializing empty queue data structure

Set ‘ans’ variable to 0. 

 

ans = 0 

 

Step 2: Enqueue root node to the queue and process it in a while loop until there are no elements left and perform the same process for the other nodes, ie.  

Enqueue root node 12 

Enqueue root node to the queue

currSize = 1

 

Step 3: Run a while loop until currSize = 0, and till then keep dequeuing elements and after processing the elements when the value of currSize = 0, increment the value of ans

Therefore, dequeue 12, and check for its left child which is 13 and the right child which is 14, and enqueue them

dequeuing elements

Now:

currSize = 0

currNode = 12

Since, currSize = 0

ans = 1 

At next iteration currSize = 2 

next iteration

Dequeue 13 and repeat steps 2 and 3 

Now:  

currSize = 1

currNode = 13 

Again, dequeue 14 and repeat steps 2 and 3 

Now: 

currSize = 0

currNode = 14 

Since, currSize = 0

ans = 2 

Dequeue last step

Follow, the steps repeatedly until there are no nodes to enqueue into the queue, after all the steps 

ans = 4 

 

final queue is empty

Therefore, we receive ans = 4, ie height of the binary tree is 4.

Python Code (without Recursion): 

# Import Collections libaray to use Queue Datastructure
import collections
 
# define a Class Tree, to intiate the binary tree
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
 
def height(root):
    # Set result variable to 0
    ans = 0
    # Initialise the queue
    queue = collections.deque()
    # Check if the tree has no nodes
    if root is None:
        return ans
 
    # Append the nodes to queue and process it in while loop until its empty
    queue.append(root)
 
    # Process in while loop until there are elements in queue
 
    while queue:
        currSize = len(queue)
        # Unless the queue is empty
        while currSize > 0:
            # Pop elements one-by-one
            currNode = queue.popleft()
            currSize -= 1
 
            # Check if the node has left/right child
            if currNode.left is not None:
                queue.append(currNode.left)
            if currNode.right is not None:
                queue.append(currNode.right)
 
        # Increment ans when currSize = 0
        ans += 1
    return ans
 
# Test the algorithm
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
 
print("Height of the binary tree is: " + str(height(root)))

 

Output: Height of a simple binary tree:

height of a binary tree is 3

 

Height of the binary tree is: 3

 

Time and Space Complexity:

The time complexity of the algorithm is O(n) as we iterate through node of the binary tree calculating the height of the binary tree only once.

And the space complexity is also O(n) as we are using an extra space for the queue. 

Where n is the number of nodes in the binary tree.

Applications of Binary Tree:

  1. Its used in many search applications and algorithms which constantly display and store data. For instance, map including set objects in many libraries.
  2. Its utilized in 3D video game to conclude which objects need to be executed.
  3. Its used in nearly every high-bandwidth router to store router tables.
  4. Its used in construction of compilers and (implicit) calculators to parse declarations.

Conclusion:

In this tutorial, we learned how to find the level order traversal of a binary tree, a basic introduction of binary trees and its applications. We also learned the meaning of height of a binary tree using two approaches, first where we apply depth first search using recursive and  in second approach we apply breadth first search without recursion using a queue data structure.

FavTutor - 24x7 Live Coding Help from Expert Tutors!

About The Author
Apurva Sharma
Hi, I am Apurva Sharma, a data science engineer, deep learning evangelist and DevOps enthusiast