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
2
3
4
5
6
    3
/ \
9 20
/ \
15 7
minimum depth = 2

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//    O    O    O
// / / \
// O O O
// 1 2 2 depth
public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) {
return 1;
}

int minVal = Integer.MAX_VALUE;

// Not necessary. two children could not be null at the same time now.
// if (root.left == null && root.right == null) {
// minVal = 0;
// }

if (root.left != null) { // if root.left is null, there is no path at all.
minVal = Math.min(minVal, minDepth(root.left));
}
if (root.right != null) {
minVal = Math.min(minVal, minDepth(root.right));
}

return minVal + 1;
}

BFS

Note:

  • Notice when to increase the depth variable.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int minDepth(TreeNode root) {
if (root == null) {
return 0;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
int depth = 0;
while (queue.size() > 0) {
// new layer
++depth;
int levelSize = queue.size();
for (int i = 0; i < levelSize; ++i) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) {
return depth;
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
}
return depth;
}

Comment