Java problem of the week - Minimum Depth of a Tree

There's something about Tree based problems that makes them very popular with interviewers. Most tree based coding problems need about 20 lines of code to answer correctly, and yet they require a fairly decent knowledge of Computer Science fundamentals.

Most tree based coding problems can be solved easily with recursion. There are times, however, when you need to use your iteration and loop ninjitsu to traverse a tree. Let's tackle a classic phone interview problem this week - iteratively finding the minimum depth of a Binary Tree.

The problem statement is as follows : 

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.

While we're at it, let's take a look at an example.

Example:

      1
     / \
    2   3 
   / \
  4   5

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

Approach

So, how do we go about solving this? There are only two classic ways to traverse a Binary Tree iteratively - Breadth First and Depth First. The former uses a Queue while the latter uses a Stack. 

Let's ask ourselves - is this a BFS problem or a DFS problem? Take a look at the graphic below. Let's assume we start our traversal at the root of the tree - which has a data value of 1. As we travel down, we should exit immediately as soon as we find a leaf node. The leaf nodes are highlighted in red - 3 or 6. With level order traversal, if we can maintain a record of the current level, as soon as we hit a leaf node we can return the current level. In the example below, when a leaf node is encountered, the level would read 3. This helps us answer our original question. This is a classic BFS problem. 

With that, let's look at the final solution for this problem. There are many patterns here that are common to MANY tree traversal problems. Want to print a binary tree? Want to find the sum of all nodes in a level? These are all problems that can be solved with the 2 Queue approach for level order traversal. 

Your Turn!

Let's try it out! Minimize this window and try to write the code yourself. If you're stuck, check out the code hints below. This problem is also available within www.firecode.io 's Java language track. Sign up to solve this in your browser.

Stuck? Here's a hint

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.

Still stuck? Let's go over the solution step by step

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. Set up 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.

Solution

public static int minTreeDepth(TreeNode root) {
    if(root == null) return 0;
    int depth = 1;
    Queue curLevel = new LinkedList<>();
    Queue nextLevel = new LinkedList<>();
    curLevel.add(root);
    while(!curLevel.isEmpty()){
        TreeNode t = curLevel.poll();
        if(t.left == null && t.right == null) return depth;
        else {
            if(t.left != null) nextLevel.add(t.left);
            if(t.right != null) nextLevel.add(t.right);
            if(curLevel.isEmpty()){
                depth++;
                curLevel = nextLevel;
                nextLevel = new LinkedList<>();
            }
        }
    }
    return depth;
}

Efficiency

Let's discuss the runtime complexity. Since we're visiting at most N nodes in a binary tree of size N, the runtime complexity is linear, or O(n). As far as space goes, our Queues can never have more than N elements. So the space complexity is also linear, or O(n). 

So there you have it! Congratulations on solving a classic coding interview problem. Want more like this? Sign up for Firecode.io and start solving for FREE today. Have a better solution? Notice any errors? That's what the comments are for!

 - Ackshaey