111. Minimum Depth of Binary Tree

Published on July 17, 2023

Question

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 1:

Input: root = [3,9,20,null,null,15,7]
Output: 2

Example 2:

Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5

Algorithm

So this question is easy at first glance but there is a trap.

I wrote a simple recursion like

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

However, there is a example2 that we cannot apply this calculation and get the right answer. So we need to take care of those node who has only single child.

Basically we use recursion to record the depth for each node until we reach the leaf nodes.

You could find that in such problems(using recursion), we tends to handle the base case first and then take care of the left and right node of current node. That's the nature of recursion also a way of traverse the binary tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return 1;
        int left = Integer.MAX_VALUE;
        int right = Integer.MAX_VALUE;
        if (root.left != null) {
            left = minDepth(root.left);
        }
        if (root.right != null) {
            right = minDepth(root.right);
        }
        
        return Math.min(left, right) + 1;
    }
}