5.10 Minimum Depth of Binary Tree

5.10.1 Problem Metadata

• Platform: LeetCode
• Problem ID: 111
• Difficulty: Easy
• URL: https://leetcode.com/problems/minimum-depth-of-binary-tree/
• Tags:
• Techniques: Depth First Search, DFS, Tree

5.10.2 Description

Return the minimum depth from root to the nearest leaf.

5.10.3 Solution - DFS

5.10.3.1 Walkthrough

Return 0 for a null node. If one child is null, the minimum depth must go through the other child. Otherwise, take 1 + min(leftDepth, rightDepth).

5.10.3.2 Analysis

• Time Complexity: O(n)
• Space Complexity: O(h)

5.10.3.3 Code - Java

public int minDepth(TreeNode root) {
    if (root == null) {
        return 0;
    }
    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));
}