# 12. Minimum depth in a binary tree

111\. Minimum Depth of Binary TreeEasy5.8K1.1KCompanies

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

![](https://assets.leetcode.com/uploads/2020/10/12/ex_depth.jpg)

<pre><code><strong>Input: root = [3,9,20,null,null,15,7]
</strong><strong>Output: 2
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: root = [2,null,3,null,4,null,5,null,6]
</strong><strong>Output: 5
</strong></code></pre>

**Constraints:**

* The number of nodes in the tree is in the range `[0, 105]`.
* `-1000 <= Node.val <= 1000`

{% embed url="<https://leetcode.com/problems/minimum-depth-of-binary-tree/description/>" %}

### DFS

> Time: O(V)

> Space: O(H), recursion stack

```jsx
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */

// DFS
var minDepth = function(root) {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;

    return findMinDepth(root, 1);
};

function findMinDepth(node, step = 1) {
    if (node === null) {
        return 0;
    }

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

    const left = findMinDepth(node.left, step + 1);
    const right = findMinDepth(node.right, step + 1);
    // console.log(left, right);

    if (left === 0) return right;
    if (right === 0) return left;
    return Math.min(left, right);
}
```

### BFS

> Time: O(V), height of tree

> Space: O(v), v is num of nodes

```jsx
// BFS
var minDepth = function(root) {
    if (root === null) return 0;
    if (root.left === null && root.right === null) return 1;

    const q = [[root, 1]];

    while (q.length > 0) {
        const [node, step] = q.shift();
        
        if (node.left === null && node.right === null) {
            return step;
        }
        
        if (node.left !== null) {
            q.push([node.left, step + 1]);
        }
        
        if (node.right !== null) {
            q.push([node.right, step + 1]);
        }
    }

    return 0;
};
```