# Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Note: A leaf is a node with no children.

The minimum depth of the binary tree is 3. Now there are total three paths where we have a total of 3 nodes from root to leaf.

``````6 -> 2 -> 0
6 -> 8 -> 7
6 -> 8 -> 9``````

A small recursive `DFS` solution is good to find the answer.

```public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null) {
return minDepth(root.right) + 1;
}
if (root.right == null) {
return minDepth(root.left) + 1;
}
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
}
```

The drawback of the `DFS` approach in this case is that all nodes should be visited to ensure that the minimum depth would be found. Therefore, this results in a `O(N)` complexity. One way to optimize the complexity is to use the `BFS` strategy. We iterate the tree level by level, and the first leaf we reach corresponds to the minimum depth. As a result, we do not need to iterate all nodes.

```class Solution {
public int minDepth(TreeNode root) {

if(root == null){
return 0;
}
queue.offer(root);
int depth = 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i = 0 ; i < size ; i++){
TreeNode curNode = queue.poll();
if(isLeaf(curNode)){
return depth;
}
if(curNode.left != null){
queue.offer(curNode.left);
}
if(curNode.right != null){
queue.offer(curNode.right);
}
}
depth++;
}
return 0;
}

private boolean isLeaf(TreeNode node){
return node != null && node.left == null && node.right == null;
}
}
```

Complexity analysis

• Time Complexity : `O(N)`.
• Space Complexity : `O(N)`.

In the worst case of the BFS method, we have a tree like this:

``````   1
\
2
\
3
\
4
``````

And in this case, we need to visit every node until we get to the only leaf node. So we need to visit `N` nodes in the worst case.

Categories: Binary Tree