Difficulty: Medium, Asked-In: Amazon, VMWare, Zoho, Synopsys.
Key takeaway: One of the fundamental tree problems to learn problem-solving using DFS (Postorder) and BFS traversal.
Given a binary tree, write a program to find its height. In other words, we need to calculate the maximum depth of the binary tree.
In the above diagram, 5, 8, and 9 are leaf nodes.
The maximum count of edges from root to farthest leaf = max(3, 3, 2) = 3.
So, the height of the given binary tree = 3.
A binary tree is a recursive structure where we can solve the problem using the solution of two smaller subproblems: the left sub-tree and the 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. The height of the tree = The longest path from the root node 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. In other words, before calculating the height of the tree, we should calculate the height of the left and right sub-trees. So we need to apply the idea of post-order traversal. Explore and think!
Suppose we are using the function int treeHeight(TreeNode root).
If tree is empty or tree has only one node, we return 0. This would be our base case. 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)
int treeHeight(TreeNode root)
{
if(root == NULL || (root->left == NULL && root->right == NULL))
return 0
else
{
int leftHeight = treeHeight(root->left)
int rightHeight = treeHeight(root->right)
if(leftHeight > rightHeight)
return (leftHeight + 1)
else
return (rightHeight + 1)
}
}
We are doing post-order traversal to find the height i.e. visiting each node using post-order and doing O(1) operation with each node. So time complexity = n*O(1) = O(n). Space complexity is equal to the size of the recursion call stack, which is equal to the height of the tree.
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! As we know, the height of the binary tree = The total number of levels in the binary tree - 1. So one idea is: We traverse the tree using level order traversal, count the total number of levels and calculate the height.
Here we traverse the tree level by level and increment a level count by 1 whenever we reach a new level. So how do we identify the situation when we reach a new level? Here is the idea: Suppose level order traversal is at the start of some level x. Now after processing all the nodes at level x, we will reach new level x + 1.
To implement this, we count nodes at the current level x, and using a loop, we add the next-level nodes to the queue until the count of nodes at the current level is 0. Now level order traversal has processed all the nodes at level x and it is at the start of the next level x + 1. At this stage, we increment the level count by 1. We keep repeating this process whenever we encounter a new level. At the start, the value of the level count is initialized to 0.
Now we run a while loop till the Q becomes empty. At each iteration of this loop will explore one level of the binary tree.
levelCount = levelCount + 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)
}
int treeHeight(TreeNode root)
{
if (root == NULL || (root->left == NULL && root->right == NULL))
return 0
int levelCount = 0
queue<TreeNode> Q
Q.enqueue(root)
while(Q.empty() == false)
{
levelCount = levelCount + 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 levelCount - 1
}
Time complexity = Time complexity of the level order traversal = O(n).
Space complexity = Space complexity of the level order traversal.
int treeHeight(TreeNode root)
{
if (root == NULL)
return 0
queue<TreeNode> Q
Q.enqueue(root)
// Marker for the end of the current level
Q.enqueue(NULL)
int height = 0
while (Q.empty() == false)
{
TreeNode temp = Q.dequeue()
if (temp == NULL)
{
// Finished traversing the current level
height = height + 1
// If there's more to process, add another NULL marker
if (Q.empty() == false)
Q.enqueue(NULL)
}
else
{
// Enqueue left and right children if they exist
if (temp->left)
Q.enqueue(node->left)
if (temp->right)
Q.enqueue(node->right)
}
}
return height
}
Enjoy learning! Enjoy algorithms!