Minimum Depth of Binary Tree

The minimum depth of a binary tree is the number of nodes along the shortest path from the root node down to the nearest leaf node. This problem is a classic tree traversal exercise, useful for understanding depth-first search (DFS) and breadth-first search (BFS) techniques in tree structures. Your task is to write an algorithm to determine this minimum depth.

Problem Description

Given the root of 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. A leaf node is a node with no children.

What needs to be achieved:

• Calculate the minimum number of nodes required to reach a leaf node from the root.
• Return this minimum depth as an integer.

Key Requirements:

• The input is a binary tree represented as a root node.
• The tree may be empty.
• The tree may contain leaf nodes that are not directly connected to other nodes.

Expected Behavior:

• If the tree is empty (root is null), return 0.
• If the root is a leaf node, return 1.
• For a non-empty tree, traverse the tree to find the shortest path to a leaf node.

Edge Cases to Consider:

• Empty tree.
• Tree with only a root node (which is also a leaf).
• Trees where the shortest path to a leaf is on the left or right subtree.
• Trees with unbalanced structure.

Examples

Example 1:

Input: root = [3,9,20,null,null,15,7]
       3
      / \
     9  20
       /  \
      15   7
Output: 2
Explanation: The shortest path is 3 -> 9, which has a depth of 2.

Example 2:

Input: root = [2]
Output: 1
Explanation: The tree consists of only the root node, which is also a leaf node.

Example 3:

Input: root = [1,null,2]
Output: 1
Explanation: The shortest path is 1 -> 2, which has a depth of 2.

Example 4: (Edge Case - Empty Tree)

Input: root = null
Output: 0
Explanation: The tree is empty.

Constraints

• The number of nodes in the tree will be in the range [0, 10⁴].
• The values of the nodes are non-negative integers.
• The solution should have a time complexity of O(N), where N is the number of nodes in the tree. (While a recursive solution is common, consider iterative approaches for potential performance gains in some languages).

Notes

You can solve this problem using either Depth-First Search (DFS) or Breadth-First Search (BFS). DFS is often more intuitive for this problem. Consider how to handle cases where you encounter a leaf node early in the traversal – you want to ensure you're tracking the minimum depth. Think about how to avoid unnecessary exploration of branches that are already deeper than the current minimum depth found. A recursive approach can be elegant, but be mindful of potential stack overflow issues with very deep trees.