---
# System prepended metadata

title: LC 111. Minimum Depth of Binary Tree
tags: [easy, BFS, Binary Tree, leedcode, python, c++]

---

# LC 111. Minimum Depth of Binary Tree

### [Problem link](https://leetcode.com/problems/minimum-depth-of-binary-tree/)

###### tags: `leedcode` `easy` `python` `c++` `Binary Tree` `BFS`

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.

 **Note:** A leaf is a node with no children.

**Example 1:** 
<img alt="" src="https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg" style="width: 432px; height: 302px;" />
```
Input: root = [3,9,20,null,null,15,7]
Output: 2
```

**Example 2:** 

```
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
```

 **Constraints:** 

- The number of nodes in the tree is in the range <code>[0, 10<sup>5</sup>]</code>.
- <code>-1000 <= Node.val <= 1000</code>

## Solution 1
#### C++
```cpp=
class Solution {
public:
    int minDepth(TreeNode* root) {
        int res = 0;
        queue<TreeNode *> q;

        if (root != nullptr) {
            q.push(root);
        }
        while (!q.empty()) {
            int size = q.size();
            res++;

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

                if (node->left == nullptr && node->right == nullptr) {
                    return res;
                }
                if (node->left != nullptr) {
                    q.push(node->left);
                }
                if (node->right != nullptr) {
                    q.push(node->right);
                }
            }
        }
        return res;
    }
};
```

>### Complexity
>w = maximum width of binary tree
>|             | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1  | O(n)            | O(w)             |

## Note
找最短xx的BFS就對了
