algoadvance

Leetcode 111. Minimum Depth of Binary Tree

Problem Statement

Given 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 is a node with no children.

For example, given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its minimum depth which is 2.

Clarifying Questions

  1. Can the binary tree be empty (i.e., the root is nullptr)?
    • Yes, it’s possible.
  2. What should be returned if the tree is empty?
    • Return 0 since there are no nodes in the tree.

Strategy

  1. Breadth-First Search (BFS):
    • The BFS approach is ideal here as it explores nodes level by level.
    • We can use a queue to perform level-order traversal and stop as soon as we encounter the first leaf node.
    • This approach ensures that we find the shortest path to a leaf node efficiently.
  2. Depth-First Search (DFS):
    • Alternatively, we could consider a recursive DFS solution.
    • We would explore each path from the root to the leaves, keeping track of the minimum depth.

Let’s implement the BFS approach for simplicity and efficiency in finding the shortest path.

Code

#include <queue>

// 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 == nullptr) return 0;
        
        std::queue<TreeNode*> q;
        q.push(root);
        int depth = 1;
        
        while (!q.empty()) {
            int levelSize = q.size();
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* currentNode = q.front();
                q.pop();
                
                // Check if it's a leaf node
                if (currentNode->left == nullptr && currentNode->right == nullptr) {
                    return depth;
                }
                
                // Add left and right children to the queue if they exist
                if (currentNode->left != nullptr) q.push(currentNode->left);
                if (currentNode->right != nullptr) q.push(currentNode->right);
            }
            ++depth; // Increment depth at the end of each level
        }
        
        return depth;
    }
};

Time Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI