# 111. Minimum Depth of Binary Tree

Reference: LeetCode

Difficulty: Easy

## Problem

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.

**Example:**

1 | 3 |

## Analysis

**Methods:**

- Recursion
- A minimum depth of a tree is the minimum of the minimum depths of two subtrees plus one.
- If
`x.left`

or`x.right`

is`null`

, we don’t need to calculate the depth of it, since there is no path. `minDepth(x)`

= min(`minDepth(x.left)`

,`minDepth(x.right)`

) + 1**Time:**$O(N)$**Space:**$O(h)$

- DFS
- All nodes are traversed to ensure that the minimum depth would be found.
**Time:**$O(N)$**Space:**$O(h)$

- BFS
- We iterate the tree level by level, and the first leaf we reach corresponds to the minimum depth. So we don’t need to iterate all nodes.
**Time:**$O(N)$**Space:**- Best: $O(1)$ (spindly tree)
- Worst: $O(N)$. The queue contains all nodes in the bottom level which is $N / 2$ nodes for a balanced tree. (bushy tree)

## Code

### Recursion

**Note:**

- Notice the
`null`

check. If a subtree is`null`

, we cannot update`minDepth`

with it since there is no path and it does not count to the minimum.

1 | // O O O |

### BFS

**Note:**

- Notice when to increase the depth variable.

1 | public int minDepth(TreeNode root) { |

Comment