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;
}