Minimum Depth of Binary Tree

• 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).

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    public int minDepth(TreeNode root) {18        if (root == null) {19            return 0;20        }21        22        int leftDepth = minDepth(root.left);23        int rightDepth = minDepth(root.right);24        25        // If one of the subtrees is empty, we must consider the other one.26        // A node with one child is not a leaf, so its path continues.27        if (leftDepth == 0 || rightDepth == 0) {28            return 1 + leftDepth + rightDepth;29        }30        31        // If both subtrees are non-empty, we take the minimum path.32        return 1 + Math.min(leftDepth, rightDepth);33    }34}