Minimum Depth of a Tree

Write a non-recursive method minTreeDepth that takes in the root node of a Binary Tree and returns the minimum depth of the tree. The minimum depth is defined as the least number of node traversals needed to reach a leaf from the root node. Your method should run in linear O(n) time and use at max O(n) space.

Example:

      1
     / \
    2   3 
   / \
  4   5

Output : 2
1 -> 3 is the minimum depth, with a 2 node traversal.

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

Since you've been asked to find the Minimum Depth, your method should exit as soon as it finds a node with null left and right children. This then becomes a class BFS problem. When dealing with a tree BFS problem, you should immediately think of Level Order Traversal. Two Queues can be used to traverse a tree in Level Order. The first Queue holds the TreeNode s of the current level, and the second Queue holds those of the next level. When skipping to the next level, simply set the next level Queue to the current level Queue and create a new Queue for the next Level.

Final hint! You should be able to code the problem on viewing this.

1. Initialize a variable depth to 1.

2. Create a Queue for the current level - Queue curLevel = new LinkedList<>();

3. Create a Queue for the next level - Queue nextLevel = new LinkedList<>();

4. Add root to curLevel. Setup a while loop that loops until curLevel becomes empty. Within the while loop, if you encounter a node with null left and right nodes, return the depth up til that point.

5. Inside the loop, .poll() a TreeNode from curLevel. If its left and right nodes are not null, add them to nextLevel. Check once again if curLevel is empty. If it is, we need to move over to the next level. Set curLevel to nextLevel and create a new LinkedList<>() for nextLevel, while incrementing depth by 1.

public int minTreeDepth(TreeNode root) {
    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Minimum Depth of a Tree

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :