Write a non-recursive method **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.

`minTreeDepth`

that takes in the root node of a Binary Tree and returns the Example:

1

/ \

2 3

/ \

4 5

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

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

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.
1. Initialize a variable

2. Create a Queue for the current level -

3. Create a Queue for the next level -

4. Add

5. Inside the loop,

`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) { }

**C**

**Java**

**Python**