Difficulty: Medium, Asked-In: Amazon, VMWare, Zoho, Synopsys
Key takeaway: One of the fundamental tree problems to learn problem-solving using DFS (Postorder traversal) and BFS traversal.
Given a binary tree, write a program to find its height.
Example
The leaf nodes of the binary tree are 5, 8, and 9.
The maximum number of nodes from root to farthest leaf = max(4, 4, 3) = 4. Hence, the height of the binary tree is 4.
Solution Idea
A binary tree is a recursive structure where we can solve the problem using the solution of two smaller subproblems: left sub-tree and right sub-tree. So how can we apply this idea to find the height of a binary tree? Let's think!
Based on the definition, for finding the height, we should know the path length of the root to the deepest leaf node, which can be either present in the left-subtree or right sub-tree. In other words, the longest path from the root to the deepest leaf can go through either the left or right child of the root.
So the best idea would be to calculate the height of the left and right sub-tree recursively. Whichever sub-tree has the maximum height, we take that value and add 1 to get the height of the tree. Here is a clear insight:
The height of the tree = the longest path from the root node to the leaf node = 1 + max (longest path from the left-child to the leaf node, longest path from the right-child to the leaf node) = 1 + max (height of the left sub-tree, height of the right sub-tree)
So if we know the height of the left and right sub-tree then we can easily find the height of the tree. But one idea would be clear: before calculating the height of the tree, we must know the height of the left and right sub-tree. For this, we can use the post-order traversal. Think!
Solution Steps
Suppose we are using the function int treeHeight(TreeNode root).
Otherwise, we traverse the tree in a post-order fashion and call the same function for the left and right child to calculate the height of the left and right sub-tree.
int leftHeight = treeHeight(root->left)
int rightHeight = treeHeight(root->right)
Now after calculating the height of the left and right subtree, we take the maximum height among both and return the value by adding one to it.
if (leftHeight > rightHeight)
return (leftHeight + 1)
else
return (rightHeight + 1)
Solution Pseudocode
int treeHeight(TreeNode root)
{
if (root == null)
return 0
else
{
int leftHeight = treeHeight(root->left)
int rightHeight = treeHeight(root->right)
if (leftHeight > rightHeight)
return (leftHeight + 1)
else
return (rightHeight + 1)
}
}
Solution Analysis
We are doing post-order traversal for finding the height of the tree. So time complexity = O(n). Space complexity is equal to the size of the recursion call stack, which is equal to the height of the tree.
Explore this blog for better understanding: Recursive Tree Traversals of a Binary Tree
Solution Idea
Now a critical question is: can we find the height of the tree without recursion? Can we use level order traversal to find height? Let's think!
The idea is: while doing the level order traversal, whenever we move down to a level, we increase height by 1. We count the number of nodes at the current level, and using a loop, we start adding next-level nodes to the queue till the count of nodes at the current level is 0.
After this, we move to the next level and again increase the height by 1. In simple words, we continue a similar process whenever we encounter a new level in the tree. At the start, the value of height is initialized as 0.
Solution Steps
We create a queue Q and push the root node into it. We also initialize a variable height with 0 to track the height of the tree.
if(root == NULL)
return 0
int height = 0
Queue Q
Q.enqueue(root)
Now we run a while loop till the Q becomes empty. In other words, this loop will explore every level. At each iteration of this loop:
height = height + 1
int nodeCount = queue.size()
for(int i = 0; i < nodeCount; i = i + 1)
{
TreeNode temp = Q.dequeue()
if(temp->left != NULL)
Q.enqueue(temp->left)
if(temp.right != NULL)
Q.enqueue(temp->right)
}
Solution Pseudocode
int treeHeight(TreeNode root)
{
if(root == NULL)
return 0
int height = 0
Queue Q
Q.enqueue(root)
while(Q.empty() == false)
{
height = height + 1
int nodeCount = Q.size()
for(int i = 0; i < nodeCount; i = i + 1)
{
TreeNode temp = Q.dequeue()
if(temp->left != NULL)
Q.enqueue(temp->left)
if(temp->right != NULL)
Q.enqueue(temp->right)
}
}
return height
}
Solution Analysis
Time complexity = Time complexity of the level order traversal = O(n)
Space complexity = Space complexity of the level order traversal
Explore this blog for better understanding: Level Order Traversal of a Binary Tree
Enjoy learning! Enjoy algorithms!
Subscribe to get weekly content on data structure and algorithms, machine learning, system design and oops.