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:
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.
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:
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.
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.
Step 3: The node ‘d’ asks the same questions to it’s left and right child ie.
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
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:
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 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:
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.
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
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
Now:
currSize = 0
currNode = 12
Since, currSize = 0
ans = 1
At next iteration currSize = 2
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
Follow, the steps repeatedly until there are no nodes to enqueue into the queue, after all the steps
ans = 4
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 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:
- Its used in many search applications and algorithms which constantly display and store data. For instance, map including set objects in many libraries.
- Its utilized in 3D video game to conclude which objects need to be executed.
- Its used in nearly every high-bandwidth router to store router tables.
- 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.
