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. In other words, we are given a binary tree and we need to calculate the maximum depth of the binary tree.
The leaf nodes of the binary tree are 5, 8, and 9.
The maximum number of edges from root to farthest leaf = max(3, 3, 2) = 3. So, the height or maximum depth of the given binary tree is 3.
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. So we need to traverse tree using post-order traversal. Think!
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)
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);
}
}
def treeHeight(root):
if root is None or (root.left is None and root.right is None):
return 0
else:
leftHeight = treeHeight(root.left)
rightHeight = treeHeight(root.right)
if leftHeight > rightHeight:
return leftHeight + 1
else:
return rightHeight + 1
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 Traversal of a Binary 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 from the binary tree property => The height of the binary tree = The total number of levels in the binary tree - 1. The idea is: We traverse tree using level order traversal, count total number of levels and return the height of the tree using the above formula.
So we traverse binary tree level by level and increment a level count by 1 whenever we reach a new level. To determine the next level from the current one, we count the number of nodes at the current level, and using a loop, we add the next-level nodes to the queue until the count of nodes at the current level is 0. Then, we move on to the next level and increment the level count by 1. This process is repeated whenever we encounter a new level in the tree. At the start, the value of the level count is initialized to 0.
Explore this blog for better understanding: Level Order Traversal of a Binary Tree
We create a queue Q and push the root node into it. We also initialize a variable levelCount with 0 to track the level count of the tree.
if (root == NULL || (root->left == NULL && root->right == NULL))
return 0
int levelCount = 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:
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.push(root);
while(!Q.empty())
{
levelCount = levelCount + 1;
int nodeCount = Q.size();
for(int i = 0; i < nodeCount; i = i + 1)
{
TreeNode* temp = Q.front();
Q.pop();
if(temp->left != NULL)
Q.push(temp->left);
if(temp->right != NULL)
Q.push(temp->right);
}
}
return levelCount - 1;
}
def treeHeight(root):
if root is None or (root.left is None and root.right is None):
return 0
levelCount = 0
Q = deque()
Q.append(root)
while Q:
levelCount = levelCount + 1
nodeCount = len(Q)
for i in range(nodeCount):
temp = Q.popleft()
if temp.left is not None:
Q.append(temp.left)
if temp.right is not None:
Q.append(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
Enjoy learning! Enjoy algorithms!