# Java problem of the week - Minimum Depth of a Tree

Ackshaey Singh | @ackshaey | 10 May, 2016

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   5Output : 21 -> 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 `Queue`s 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