Minimum Depth of Binary Tree

The problem asks us to find the minimum depth of a binary tree. 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.

Naive Solution

A naive solution would be to traverse the tree and find all paths from the root to the leaves. Then, we can find the length of the shortest path. This can be done using Depth-First Search (DFS).

Optimal Solution

A more efficient approach is to use Breadth-First Search (BFS). BFS explores the tree level by level. As soon as we encounter a leaf node, we know that the current level represents the minimum depth because BFS explores all shallower levels before deeper ones.

Edge Cases

• If the root is null, the minimum depth is 0.
• If the root has only one child, the minimum depth is the minimum depth of the subtree plus 1.

Code (Java)

import java.util.LinkedList;
import java.util.Queue;

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;
        }

        Queue<TreeNode> queue = new 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 depth;
    }
}

Code (Python)

from collections import deque

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

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

        return 0

Time and Space Complexity

• Time Complexity: O(N), where N is the number of nodes in the tree. In the worst case, we may need to visit all nodes.
• Space Complexity: O(W), where W is the maximum width of the tree. In the worst case (a complete binary tree), W is proportional to N, so the space complexity can be O(N).