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 5
Output : 2
1 -> 3 is the minimum depth, with a 2 node traversal.
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.
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.
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.
depth
to 1.Queue curLevel = new LinkedList<>();
Queue nextLevel = new LinkedList<>();
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. .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 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; }
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