Minimum Depth of a Binary Tree

Given a binary tree, return its minimum depth: the number of nodes on the shortest path from the root down to the nearest leaf. An empty tree has depth 0.

LeetCode: 111. Minimum Depth of Binary Tree

Example

Text

    3
   / \
  9   20          Output: 2   (3 -> 9)
     /  \
    15   7

  2
   \
    3             Output: 3   (2 -> 3 -> 4), not 1: the root isn't a leaf
     \
      4

Brute force: recursive DFS

The minimum depth is 1 + min(left, right), except when one child is missing. A missing child isn't a leaf, so it can't end a path. Taking min(0, ...) there would give the wrong answer for the second example.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null, and the empty tree is a null root.

Java

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        if (root.left == null) return 1 + minDepth(root.right);
        if (root.right == null) return 1 + minDepth(root.left);
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

    public static void main(String[] args) {
        TreeNode a = node(3, leaf(9), node(20, leaf(15), leaf(7)));
        TreeNode b = node(2, null, node(3, null, leaf(4)));
        System.out.println(minDepth(a) + " " + minDepth(b) + " " + minDepth(null));
    }
}

Output

2 3 0

Time: O(n): it visits every node, even when a leaf sits right below the root. Space: O(h).

Optimal: BFS, stop at the first leaf

Breadth-first search visits the tree level by level, so the first leaf it reaches is the shallowest one. Nothing below that level is visited. The queue is an ArrayDeque, a resizable array used as a queue. The depth is the number of levels processed so far.

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    static TreeNode node(int val, TreeNode left, TreeNode right) {
        return new TreeNode(val, left, right);
    }

    static TreeNode leaf(int val) {
        return new TreeNode(val, null, null);
    }

    static int minDepth(TreeNode root) {
        if (root == null) return 0;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            for (int i = queue.size(); i > 0; i--) {
                TreeNode n = queue.poll();
                if (n.left == null && n.right == null) return depth;
                if (n.left != null) queue.add(n.left);
                if (n.right != null) queue.add(n.right);
            }
            depth++;
        }
        return 0;
    }

    public static void main(String[] args) {
        TreeNode a = node(3, leaf(9), node(20, leaf(15), leaf(7)));
        TreeNode b = node(2, null, node(3, null, leaf(4)));
        System.out.println(minDepth(a) + " " + minDepth(b) + " " + minDepth(null));
    }
}

Output

2 3 0

Time: O(n) in the worst case, but it stops at the first leaf's level. Space: O(w) for the widest level visited.

ArrayDeque rejects null, so the code checks each child before adding it. queue.size() is read once when the for loop starts, so children added during the loop belong to the next level.

Edge cases

Empty tree: 0.
Single node: 1.
Skewed tree: its only leaf is at the bottom, so the depth is n.