Difficulty: Easy, Asked-in: Facebook, Amazon
Key takeaway: An excellent problem to learn problem-solving using both recursive and iterative tree traversal. This is also a question to understand effcient problem solving using BFS when the solution node is nearest to the root node.
Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node. The path has to end on a leaf node.
Example
A binary tree is a recursive object, so we can think to solve this problem using recursive tree traversal. In other words, we can think to solve this problem using the solution of the two smaller subproblems: finding the min-depth of the left subtree and finding the min-depth of the right sub-tree. Here is an idea: If we know the min-depth of the left and right subtree, then min-depth of the tree = 1 + min ( min-depth of the left subtree, min-depth of the right subtree).
Solution Pseudocode
int treeMinDepth(TreeNode root)
{
if(root == Null)
return 0
if(root->left == Null)
return 1 + treeMinDepth(root->right)
if(root->right == Null)
return 1 + treeMinDepth(root->left)
return 1 + min(treeMinDepth(root->left), treeMinDepth(root->right))
}
Time and space complexity analysis
We are traversing each node of the tree only once. Time complexity = O(n)
Space complexity = O(h) for recursion call stack. Space Complexity is equal to the maximum depth of the recursion tree which is equal to the height of the tree (h) where O(log n) < h < O(n).
Now a critical question is: can we think to solve this problem iteratively using the BFS traversal? How do we calculate the min-depth using this idea? or, do we really need to calculate the min-depth for each node? Is there some information hidden in the problem which could help us to solve the problem efficiently? Think!
Here is an observation: the node with a minimum depth would be always the first leaf node if we traverse the tree level by level. In other words, if we traverse the tree level by level, then we need to return the depth of the first encountered leaf node. Think!
In a practical scenario, this idea would be much more effcient in comparison to the DFS approach because, in the DFS approach, we may end up with a complete traversal of the tree even when the topmost leaf is close to the root. But BFS traversal can access the node from top to bottom in level by order and we can get the topmost leaf quickly in fewer steps.
For example, If we have a tree where the left subtree has a depth of 100 and the right subtree has a depth of 1. The DFS will first traverse all the way down the 100 left subtree nodes before finally traversing the right subtree with a small depth of 1 and figuring out it as a min depth. But in BFS, instead of traversing 101 nodes to figure out the min depth, we can get the value in two steps. Now imagine the comparison of efficiency if there are thousands of nodes in the left subtree!
Solution Pseudocode
class QueueNode
{
TreeNode node
int depth
}
int treeMinDepth(TreeNode root)
{
if (root == Null)
return 0
else
{
Queue Q
QueueNode tempQNode = QueueNode(root, 1)
Q.enqueue(temp)
while(Q.empty() == false)
{
tempQNode = Q.dequeue()
TreeNode temp = tempQNode->node
int depth = tempQNode->depth
if (temp->left == Null && temp->right == Null)
return depth
else
{
if(temp->left != NULL)
{
tempQNode->node = temp->left
tempQNode->depth = 1 + depth
Q.enqueue(tempQNode)
}
if(temp->right != NULL)
{
tempQNode->node = temp->right
tempQNode->depth = 1 + depth
Q.enqueue(tempQNode)
}
}
}
}
return 0
}
Time and space complexity analysis
In the worst case, The total number of queue operations = 2n, because each node gets inserted and deleted only once in BFS traversal. Time complexity = O(n), where n is the total number of nodes.
Space complexity = O(w) because BFS traversal requires queue size proportional to the max-width of the tree (w). (Think!)
Enjoy learning, Enjoy coding, Enjoy problem-solving!
Given an array, find the next greater element for every element in the array. The next greater element for an element is the first greater element on the right side of the array. This is one of the best problems to learn problem-solving using stack.
Write a program to find the equilibrium index of an array. An array's equilibrium index is an index such that the sum of elements at lower indexes equals the sum of elements at higher indexes. This is an excellent coding question to learn time and space complexity optimization using several approaches.
Write a program to detect the loop in a linked list. A linked list with a cycle causes iteration over the list to fail because the iteration will never reach the end of the list. Therefore, it is desirable to be able to detect that a linked list has no cycle before trying an iteration. So, we are going to discuss various algorithms to detect a loop in a singly linked list. This is also one of the best-linked list interview problems.
A Fenwick tree is a data structure that efficiently updates elements and calculates prefix sums in an array. It takes O(logn) time for both updates and range sum queries. It is also called Binary Indexed Tree (BIT), which was first described in the paper titled “A new data structure for cumulative frequency tables” (Peter M. Fenwick, 1994).
A heap is a complete binary tree structure where each element satisfies a heap property. We learn two types of the heap in programming: 1) max-heap, which satisfies the max heap property, and 2) min-heap, which satisfies the min-heap property. We use the heap to implement the priority queue efficiently.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.
