# 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⁵]</code>.
- <code>-1000 <= Node.val <= 1000</code>

## Solution 1
#### C++

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就對了