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:

## Analysis

Methods:

1. 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)$
2. DFS
• All nodes are traversed to ensure that the minimum depth would be found.
• Time: $O(N)$
• Space: $O(h)$
3. 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.

### BFS

Note:

• Notice when to increase the depth variable.

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.