Minimum Depth of Binary Tree

A straightforward recursive approach that traverses the tree using a Depth-First Search (DFS) pattern. The minimum depth is calculated by recursively finding the minimum depth of the left and right subtrees and then combining the results. A special check is needed to correctly handle nodes that have only one child, as the path must continue to a leaf node (a node with zero children).

• If the root is null, return 0.
• Recursively calculate the depth of the left subtree: left = minDepth(root.left).
• Recursively calculate the depth of the right subtree: right = minDepth(root.right).
• Handle leaf and single-child nodes: If either left or right is 0, it means one subtree is empty. The path must continue down the non-empty subtree. The depth is 1 + left + right (since one of them is 0, this correctly adds the depth of the non-empty one).
• Handle two-child nodes: If both subtrees are non-empty (left > 0 and right > 0), the minimum depth is 1 + min(left, right).

The core idea is to define a function, say minDepth(node), that computes the minimum depth of the subtree rooted at node.

• Base Case: If the current node is null, its depth is 0. This signifies the end of a path from its parent.
• Recursive Step: We recursively call minDepth for the left and right children to get their respective minimum depths.
• Combining Results: This is the crucial part. The minimum depth is the shortest path to a leaf node.
  • If a node has two children, the minimum depth is 1 + min(left_depth, right_depth).
  • However, if a node has only one child, it's not a leaf. The path must continue down that single child's branch. For example, for a tree [1, 2, null], the root's minDepth is not 1, but 2. Our logic must account for this. If minDepth(root.left) returns d and minDepth(root.right) returns 0, it means the right subtree is empty. The minimum depth is 1 + d, not 1 + min(d, 0). A clever way to combine these cases is to check if either child's depth is zero. If so, we must take the path through the non-empty child, so the depth is 1 + left_depth + right_depth (as one is zero). Otherwise, we take 1 + min(left_depth, right_depth).

/**
 * 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;
        }
        
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        
        // If one of the subtrees is empty, we must consider the other one.
        // A node with one child is not a leaf, so its path continues.
        if (leftDepth == 0 || rightDepth == 0) {
            return 1 + leftDepth + rightDepth;
        }
        
        // If both subtrees are non-empty, we take the minimum path.
        return 1 + Math.min(leftDepth, rightDepth);
    }
}