Minimum Depth of Binary Tree
The key idea
The minimum depth is the depth of the nearest leaf, where a leaf has NO children. A node with exactly one child is NOT a leaf, so you must follow its existing child instead of counting the missing side as depth 1. BFS finds the answer fastest by stopping at the first leaf it reaches.
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. A node that has exactly one child is not a leaf, so the missing side must not be counted as a path. For a one-sided node you descend into the child that exists.
Return 0 when the tree is empty (root is null).
Constraints
- The number of nodes in the tree is in the range
[0, 10^5]. -1000 <= Node.val <= 1000
Examples
Input: root = [3,9,20,null,null,15,7]
Output: 2
Input: root = [2,null,3,null,4,null,5,null,6]
Output: 5
Input: root = []
Output: 0
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM