[LeetCode] Problem 111 - Minimum Depth of Binary Tree

Posted on | In ,

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.

Example

Given binary tree [3,9,20,null,null,15,7],

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

return its minimum depth = 2.

O(n) runtime, O(log n) space – Depth-first traversal

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
1
2
3
4
5
6
7
8
9
10
11
12
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.right), minDepth(root.left)) + 1;
}

O(n) runtime, O(n) space – Breadth-first traversal

1
2
3
4
5
6
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
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
27
28
29
public int minDepth(TreeNode root) {
    if (root == null)
        return 0;

    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    TreeNode levelEnd = root;
    int depth = 1;

    while (!queue.isEmpty()) {
        TreeNode current = queue.poll();

        if (current.left == null && current.right == null)
            break;

        if (current.left != null)
            queue.offer(current.left);

        if (current.right != null)
            queue.offer(current.right);

        if (current == levelEnd) {
            levelEnd = current.right == null ? current.left : current.right;
            depth++;
        }
    }

    return depth;
}