111. Minimum Depth of Binary Tree

Description

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

Intuition

The minimum depth of a binary tree can be determined using a breadth-first search (BFS) approach. Since BFS explores the tree level by level, the first time it encounters a leaf node, it can immediately return the current depth as the minimum depth. This ensures that the shortest path to a leaf node is found efficiently.

Approach

1. Base Case: - If the tree is empty (i.e., the root is null), return 0 as the minimum depth.
2. Breadth-First Search (BFS): - Initialize a queue and add the root node to it. Start with a level variable set to 1, representing the current depth of the tree. - Use a loop to process nodes level by level. For each level, determine the number of nodes (levelSize) and process each node in the queue. - For each node, check if it is a leaf node (both left and right children are null). If a leaf node is found, return the current level as the minimum depth. - If the node has left or right children, add them to the queue for processing in the next level. - Increment the level variable after processing all nodes at the current level.
3. Return Result: - The loop will eventually find a leaf node, and the level at that point will be the minimum depth of the tree.

Complexity

Time Complexity:

The time complexity is (O(n)), where n is the number of nodes in the tree. In the worst case, all nodes are visited once.

Space Complexity:

The space complexity is (O(n)), which is the maximum number of nodes that can be stored in the queue at any time. In the worst case, this could be proportional to the number of nodes at the bottom level of the tree, which is approximately (O(n)) for a complete binary tree.

Code

C++

class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == nullptr) return 0;

        std::queue queue;
        queue.push(root);
        int level = 1;

        while (!queue.empty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode* node = queue.front();
                queue.pop();

                if (node->left == nullptr && node->right == nullptr) {
                    return level;
                }

                if (node->left != nullptr) {
                    queue.push(node->left);
                }

                if (node->right != nullptr) {
                    queue.push(node->right);
                }
            }

            level++;
        }

        return level;
    }
};

Python

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        queue = deque([root])
        level = 1

        while queue:
            levelSize = len(queue)

            for _ in range(levelSize):
                node = queue.popleft()

                if not node.left and not node.right:
                    return level

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

            level += 1

        return level

Java

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;

        Queue queue = new LinkedList<>();
        queue.add(root);
        int level = 1;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();

            for (int i = 0; i < levelSize; i++) {
                TreeNode node = queue.poll();

                if (node.left == null && node.right == null) {
                    return level;
                }

                if (node.left != null) {
                    queue.add(node.left);
                }

                if (node.right != null) {
                    queue.add(node.right);
                }
            }

            level++;
        }

        return level;
    }
}

JavaScript

function minDepth(root) {
    
    if (root === null) return 0;
    
    let queue = [root];
    let level = 1;
    
    while (queue.length > 0) {
        let levelSize = queue.length;
        
        for (let i = 0; i < levelSize; i++) {
            let node = queue.shift();
            
            if (node.left === null && node.right === null) {
                return level;
            }
            
            if (node.left !== null) {
                queue.push(node.left);
            }
            
            if (node.right !== null) {
                queue.push(node.right);
            }
        }
        
        level++;
    }
}