Just like we find the length of a list or the number of items in a python dictionary, we can find the height of a binary tree. In this article, we will formulate an algorithm to find the height of a binary tree. We will also implement the algorithm in python and execute on a given binary tree.
What is the height of a binary tree?
Height of a binary tree is defined as the maximum distance from the root node at which a node is present in the binary tree. The height of a binary tree depends on the number of nodes and their position in the tree. If a tree has an ‘n’ number of nodes, it can have a height anywhere between log(n) + 1 to n. The binary tree will have a height n if the tree is entirely skewed to either left or right. It will have a height of log(n)+1 if the nodes in the tree are properly distributed and the tree is a complete binary tree.
For example, the following binary tree has 7 elements.A binary tree with 7 elements can have any height between log(7)+ 1 that is 3 and 7. In our example, the nodes of the tree are properly distributed and the tree is completely balanced. Therefore, the height of the tree is 3.
How to calculate the height of a binary tree?
To calculate the height of a binary tree, we can calculate the heights of left and right subtrees. The maximum of the height of the subtrees can be used to find the height of the tree by adding one to it. For an empty root, we can say that the height of the tree is zero. Similarly, height of a single node will be considered as 1.
Algorithm to find the height of a binary tree
Now that we have found a way to find the height of the binary tree, we will formulate the algorithm for finding the height as follows.
- If we find an empty root node, we will say that the height of the tree is 0.
- Otherwise, we will find the height of the left subtree and right subtree recursively.
- After finding the height of the left subtree and right subtree, we will calculate their maximum height.
- We will add 1 to the maximum height. That will be the height of the binary tree.
Implementation of the algorithm in Python
Now that we have understood and formulated the algorithm, we will implement it in Python.
from queue import Queue class BinaryTreeNode: def __init__(self, data): self.data = data self.leftChild = None self.rightChild = None def height(root): if root is None: return 0 leftHeight=height(root.leftChild) rightHeight=height(root.rightChild) max_height= leftHeight if rightHeight>max_height: max_height = rightHeight return max_height+1 def insert(root, newValue): # if binary search tree is empty, create a new node and declare it as root if root is None: root = BinaryTreeNode(newValue) return root # if newValue is less than value of data in root, add it to left subtree and proceed recursively if newValue < root.data: root.leftChild = insert(root.leftChild, newValue) else: # if newValue is greater than value of data in root, add it to right subtree and proceed recursively root.rightChild = insert(root.rightChild, newValue) return root root = insert(None, 50) insert(root, 20) insert(root, 53) insert(root, 11) insert(root, 22) insert(root, 52) insert(root, 78) print("Height of the binary tree is:") print(height(root))
Height of the binary tree is: 3
Here, we have created a binary tree node. Then, we defined functions to insert elements to the binary tree. Finally, we implemented the algorithm to find the height of a binary tree in Python.
In this article, we have implemented an algorithm to find the height of a binary tree. To learn more about other data structures, you can read this article on Linked List in Python. Stay tuned for more articles on implementation of different algorithms in Python.
Recommended Python Training
Course: Python 3 For Beginners
Over 15 hours of video content with guided instruction for beginners. Learn how to create real world applications and master the basics.