> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/tree/111.-minimum-depth-of-binary-tree.md).

# 111. Minimum Depth of Binary Tree

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:**

Given binary tree `[3,9,20,null,null,15,7]`,

```
    3
   / \
  9  20
    /  \
   15   7
```

return its minimum depth = 2.

```cpp
// Recursion
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    if (!root->left) return minDepth(root->right) + 1;
    if (!root->right) return minDepth(root->left) + 1;
    return min(minDepth(root->left), minDepth(root->right)) + 1;
}
```

```cpp
// Recursion
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    int l_depth = minDepth(root->left), r_depth = minDepth(root->right);
    if (l_depth == 0 || r_depth == 0) return (l_depth ? l_depth : r_depth) + 1;
    else return min(l_depth, r_depth) + 1;
}
```

```cpp
// Recursion
void helper(TreeNode* root, int cur, int& res) {
    if (!root) return;
    ++cur;
    if (!root->left && !root->right) { // only update when the node is leaf
        res = min(res, cur);
    }
    helper(root->left, cur, res);
    helper(root->right, cur, res);
}
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    int res = 1e8, cur = 0;
    helper(root, cur, res);
    return res == 1e8 ? 0 : res;
}
```

```cpp
// Iteration (Level Order Traversal)
int minDepth(TreeNode* root) { // time: O(n); space: O(n)
    if (!root) return 0;
    queue<TreeNode*> q;
    q.push(root);
    int res = 0;
    while (!q.empty()) {
        ++res;
        int n = q.size();
        for (int i = 0; i < n; ++i) {
            TreeNode* cur = q.front(); q.pop();
            if (!cur->left && !cur->right) return res;
            if (cur->left) q.push(cur->left);
            if (cur->right) q.push(cur->right);
        }
    }
    return -1;
}
```