Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        from collections import deque
        queue = deque([(root, 1)])
        while queue:
            node, depth = queue.popleft()
            if not node.left and not node.right:
                return depth
            if node.left:
                queue.append((node.left, depth + 1))
            if node.right:
                queue.append((node.right, depth + 1))
    

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (!root) return 0;
        std::queue> q;
        q.push({root, 1});
        while (!q.empty()) {
            auto [node, depth] = q.front();
            q.pop();
            if (!node->left && !node->right) return depth;
            if (node->left) q.push({node->left, depth + 1});
            if (node->right) q.push({node->right, depth + 1});
        }
        return 0;
    }
};
    

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        java.util.Queue<TreeNode> queue = new java.util.LinkedList<>();
        queue.offer(root);
        int depth = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left == null && node.right == null) return depth;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            depth++;
        }
        return 0;
    }
}
    

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var minDepth = function(root) {
    if (!root) return 0;
    let queue = [[root, 1]];
    while (queue.length > 0) {
        let [node, depth] = queue.shift();
        if (!node.left && !node.right) return depth;
        if (node.left) queue.push([node.left, depth + 1]);
        if (node.right) queue.push([node.right, depth + 1]);
    }
    return 0;
};
    

Problem Description

Given the root of a binary tree, return its minimum depth. The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node.

• A leaf is a node with no children (both left and right are null).
• If the tree is empty (i.e., root is null), return 0.
• There is only one valid answer for each input tree.

Thought Process

To solve this problem, we need to find the shortest path from the root node to any leaf node in a binary tree. A brute-force approach might involve traversing all paths to every leaf and keeping track of the minimum length. However, this could be inefficient, especially for large trees.

Instead, we can optimize by using a Breadth-First Search (BFS) traversal. BFS explores nodes level by level, so the first time we encounter a leaf node, we can immediately return its depth—this guarantees it's the minimum possible. This is more efficient than exploring every possible path.

The key insight is that BFS naturally finds the shortest path in an unweighted tree, making it ideal for this problem.

Solution Approach

• Step 1: Check if the tree is empty (root is null). If so, return 0.
• Step 2: Initialize a queue for BFS. Each queue entry holds a node and its corresponding depth.
• Step 3: Start BFS by enqueueing the root node with depth 1.
• Step 4: While the queue is not empty:
  • Dequeue the front node and its depth.
  • If the node is a leaf (no left or right child), return the current depth. This is the minimum depth.
  • Otherwise, enqueue the left and/or right children (if they exist) with depth incremented by 1.
• Step 5: The process stops as soon as the first leaf node is found, ensuring optimal efficiency.

This approach is chosen because BFS guarantees we find the nearest (minimum) leaf first, and using a queue ensures efficient level-order traversal.

Example Walkthrough

Consider the following binary tree:

        1
       / \
      2   3
     /
    4
  

• Step 1: Start with root node 1 at depth 1.
• Step 2: Enqueue children: 2 (depth 2) and 3 (depth 2).
• Step 3: Dequeue 2; it's not a leaf. Enqueue its child 4 (depth 3).
• Step 4: Dequeue 3; it is a leaf (no children). Return depth 2.

Thus, the minimum depth is 2, corresponding to the path 1 → 3.

Time and Space Complexity

• Brute-force (DFS all paths):
  • Time Complexity: O(N), since every node must be visited to check all paths.
  • Space Complexity: O(N), due to recursion stack in the worst case (a skewed tree).
• Optimized (BFS):
  • Time Complexity: O(N), in the worst case where the shallowest leaf is at the bottom and all nodes are visited. In practice, it's often less since the search stops at the first leaf.
  • Space Complexity: O(N), for the queue storage (at most one level of nodes at a time).

The BFS approach is generally more efficient for this problem because it can terminate early.

Summary

To find the minimum depth of a binary tree, we use a BFS traversal that checks nodes level by level. As soon as a leaf node is found, we return its depth, ensuring the solution is both correct and efficient. The BFS approach leverages the properties of trees and queues to guarantee the shortest path is found with minimal computation.