Minimum Depth of Binary Tree
Easy · Trees · Tree · Depth-First Search · Breadth-First Search · Binary Tree
Problem
Given the root of a binary tree, return its minimum depth.
The minimum depth is the number of nodes on the shortest path from the root down to the nearest leaf. A leaf is a node with no children, so a node that has only one child is not a leaf. An empty tree has depth 0.
Examples
Input: root = [8,4,12,null,null,10,14,9] Output: 2
Node 4 is a leaf directly under the root, so the shortest root-to-leaf path has 2 nodes.
Input: root = [1,null,2,null,3] Output: 3
The tree is a chain. The root has a child, so it is not a leaf; the only leaf is 3, at depth 3.
Input: root = [] Output: 0
An empty tree has depth 0.
Constraints
- The number of nodes is in the range [0, 10^5]
- -1000 <= Node.val <= 1000
Approaches
- Baseline: recursion with the one-child rule — time O(n), space O(h)
Follow-up
Breadth-first search stops early here because it finds the answer in depth order. The use cases ask which leaf is the nearest, and the same question for a tree given as a parent array with any number of children per node.
Related problems
Start free on Cariara · Coding problems · System design studio
