# Minimum Depth of Binary Tree
**Difficulty:** EASY
[External](https://leetcode.com/problems/minimum-depth-of-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/minimum-depth-of-binary-tree
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Google](https://scaleengineer.com/companies/google), [Meta](https://scaleengineer.com/companies/meta), [Uber](https://scaleengineer.com/companies/uber)
---
## Problem
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.glich.co/dsa/minimum-depth-of-binary-tree/image0.jpg) 

**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 `[0, 105]`.
* `-1000 <= Node.val <= 1000`

# Approaches
## Recursive Depth-First Search (DFS)
A straightforward recursive approach that traverses the tree using a Depth-First Search (DFS) pattern. The minimum depth is calculated by recursively finding the minimum depth of the left and right subtrees and then combining the results. A special check is needed to correctly handle nodes that have only one child, as the path must continue to a leaf node (a node with zero children).
**Time:** O(N) · **Space:** O(H)
**Pros:** Conceptually simple and follows the natural recursive structure of a tree.; The code is concise and easy to write.
**Cons:** Can be inefficient as it might traverse a very deep path completely, even if a much shorter path exists in another subtree.; The worst-case space complexity of O(N) for skewed trees can lead to a stack overflow error for very deep trees.
### Explanation
The core idea is to define a function, say `minDepth(node)`, that computes the minimum depth of the subtree rooted at `node`.

- **Base Case:** If the current node is `null`, its depth is 0. This signifies the end of a path from its parent.
- **Recursive Step:** We recursively call `minDepth` for the left and right children to get their respective minimum depths.
- **Combining Results:** This is the crucial part. The minimum depth is the shortest path to a **leaf** node.
  - If a node has two children, the minimum depth is `1 + min(left_depth, right_depth)`.
  - However, if a node has only one child, it's not a leaf. The path must continue down that single child's branch. For example, for a tree `[1, 2, null]`, the root's `minDepth` is not 1, but 2. Our logic must account for this. If `minDepth(root.left)` returns `d` and `minDepth(root.right)` returns 0, it means the right subtree is empty. The minimum depth is `1 + d`, not `1 + min(d, 0)`. A clever way to combine these cases is to check if either child's depth is zero. If so, we must take the path through the non-empty child, so the depth is `1 + left_depth + right_depth` (as one is zero). Otherwise, we take `1 + min(left_depth, right_depth)`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = minDepth(root.left);
        int rightDepth = minDepth(root.right);
        
        // If one of the subtrees is empty, we must consider the other one.
        // A node with one child is not a leaf, so its path continues.
        if (leftDepth == 0 || rightDepth == 0) {
            return 1 + leftDepth + rightDepth;
        }
        
        // If both subtrees are non-empty, we take the minimum path.
        return 1 + Math.min(leftDepth, rightDepth);
    }
}
```
### Algorithm
- If the `root` is `null`, return 0.
- Recursively calculate the depth of the left subtree: `left = minDepth(root.left)`.
- Recursively calculate the depth of the right subtree: `right = minDepth(root.right)`.
- **Handle leaf and single-child nodes:** If either `left` or `right` is 0, it means one subtree is empty. The path must continue down the non-empty subtree. The depth is `1 + left + right` (since one of them is 0, this correctly adds the depth of the non-empty one).
- **Handle two-child nodes:** If both subtrees are non-empty (`left > 0` and `right > 0`), the minimum depth is `1 + min(left, right)`.

## Iterative Breadth-First Search (BFS)
This approach uses Breadth-First Search (BFS) to traverse the tree level by level. Since BFS explores nodes in increasing order of their distance from the root, the first leaf node it encounters will be at the minimum depth. This is the most efficient way to solve the problem in terms of nodes visited.
**Time:** O(N) · **Space:** O(W)
**Pros:** Guaranteed to find the shortest path first, making it optimally efficient in terms of nodes visited.; It is an iterative solution, which avoids deep recursion and the risk of stack overflow on very deep trees.
**Cons:** The space complexity can be O(N) for wide, bushy trees, which might be worse than the DFS approach for very deep, narrow trees.
### Explanation
We use a queue to perform a level-order traversal and keep track of the current depth. The algorithm starts by adding the root node to the queue with an initial depth of 1.

It then proceeds in levels. In each iteration of the main loop, we process all nodes at the current level. We find the number of nodes at the current level by checking the queue's size. Then, we loop that many times, dequeueing one node at a time.

For each node we dequeue, we check if it's a leaf node (i.e., both its left and right children are `null`). If it is a leaf, we have found the shortest path from the root to a leaf. The current depth is the minimum depth, and we can return it immediately, terminating the search early.

If the node is not a leaf, we add its non-null children to the queue. These children will be processed in the next level. After processing all nodes of a level, we increment the depth and move to the next level.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int depth = 1;
        
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode currentNode = queue.poll();
                
                // Check if it's a leaf node
                if (currentNode.left == null && currentNode.right == null) {
                    return depth;
                }
                
                // Add children to the queue
                if (currentNode.left != null) {
                    queue.offer(currentNode.left);
                }
                if (currentNode.right != null) {
                    queue.offer(currentNode.right);
                }
            }
            depth++;
        }
        
        return depth; // Should not be reached in a valid tree
    }
}
```
### Algorithm
- If the `root` is `null`, return 0.
- Initialize a `Queue` and add the `root` node.
- Initialize `depth = 1`.
- While the queue is not empty:
  - Get the number of nodes at the current level, `levelSize = queue.size()`.
  - Loop `levelSize` times to process all nodes at the current level.
    - Dequeue a node, `currentNode`.
    - If `currentNode` is a leaf (`currentNode.left == null` and `currentNode.right == null`), it's the first leaf found, so return the current `depth`.
    - If `currentNode.left` is not `null`, enqueue it.
    - If `currentNode.right` is not `null`, enqueue it.
  - After processing the entire level, increment `depth`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public int minDepth ( TreeNode root ) { if ( root == null ) { return 0 ; } if ( root . left == null ) { return 1 + minDepth ( root . right ); } if ( root . right == null ) { return 1 + minDepth ( root . left ); } return 1 + Math . min ( minDepth ( root . left ), minDepth ( root . right )); } }
```

### JavaScript

```javascript
/** * 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} */ var minDepth =
  function (root) {
    if (!root) {
      return 0;
    }
    if (!root.left) {
      return 1 + minDepth(root.right);
    }
    if (!root.right) {
      return 1 + minDepth(root.left);
    }
    return 1 + Math.min(minDepth(root.left), minDepth(root.right));
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int minDepth ( TreeNode * root ) { if ( ! root ) { return 0 ; } if ( ! root -> left ) { return 1 + minDepth ( root -> right ); } if ( ! root -> right ) { return 1 + minDepth ( root -> left ); } return 1 + min ( minDepth ( root -> left ), minDepth ( root -> right )); } };
```

### Python

```python
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right # dfs class Solution : def minDepth ( self , root : Optional [ TreeNode ]) -> int : if root is None : return 0 if root . left is None : return 1 + self . minDepth ( root . right ) if root . right is None : return 1 + self . minDepth ( root . left ) return 1 + min ( self . minDepth ( root . left ), self . minDepth ( root . right )) ########## # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class TreeNode : def __init__ ( self , val = 0 , left = None , right = None ): self . val = val self . left = left self . right = right # bfs class Solution : def minDepth ( self , root : TreeNode ) -> int : if not root : return 0 queue = deque ([( root , 1 )]) # The queue holds tuples of (node, current_depth) while queue : current_node , depth = queue . popleft () # Check if the current node is a leaf node if not current_node . left and not current_node . right : return depth # Otherwise, add the children to the queue with incremented depth if current_node . left : queue . append (( current_node . left , depth + 1 )) if current_node . right : queue . append (( current_node . right , depth + 1 )) # test case: # Construct a binary tree: [3,9,20,None,None,15,7] root = TreeNode ( 3 ) root . left = TreeNode ( 9 ) root . right = TreeNode ( 20 ) root . right . left = TreeNode ( 15 ) root . right . right = TreeNode ( 7 ) sol = Solution () print ( sol . minDepth ( root )) # Output: 2
```