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:
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:
[0, 105].-1000 <= Node.val <= 1000Problem Overview: You are given the root of a binary tree and need to return its minimum depth. The minimum depth is the number of nodes along the shortest path from the root to the nearest leaf node (a node with no children). Unlike maximum depth problems, you must stop as soon as the first leaf is encountered.
Approach 1: Breadth-First Search (BFS) (Time: O(n), Space: O(w))
BFS processes the tree level by level using a queue. Start by pushing the root node with depth 1. At each step, remove a node from the queue, check if it is a leaf, and if so return its depth immediately. Otherwise push its left and right children with depth +1. The key insight: the first leaf discovered during level-order traversal must belong to the minimum depth path. Because each node is visited once, the time complexity is O(n), where n is the number of nodes. Space complexity is O(w), where w is the maximum width of the tree. This approach naturally fits problems involving the shortest distance from a root in a tree structure.
Approach 2: Depth-First Search (DFS) (Time: O(n), Space: O(h))
DFS explores each branch recursively and calculates the minimum depth from children. For every node, compute the minimum of the left and right subtree depths and add one for the current node. The tricky part is handling nodes with only one child: if one subtree is null, you must return the depth of the non-null subtree instead of taking a minimum with zero. Without this condition, the result becomes incorrect for skewed trees. DFS visits every node once, giving O(n) time complexity. The recursion stack uses O(h) space where h is the tree height. This technique commonly appears in recursive problems involving depth-first search on a binary tree.
Recommended for interviews: BFS is usually the expected answer because it naturally finds the shortest path to a leaf and can terminate early once the first leaf is encountered. DFS still demonstrates strong understanding of recursion and tree traversal, but it always explores deeper branches even when a shallow leaf already exists. Showing both approaches during an interview signals that you understand traversal strategies and their tradeoffs.
The BFS approach utilizes a queue to perform a level-order traversal of the tree. Each node is dequeued and checked if it is a leaf node. The level count is incremented each time a complete level is processed. The algorithm stops as soon as a leaf node is found, and the current level is returned as the minimum depth.
The solution uses a queue for the BFS traversal of the tree. Each node, along with its depth, is enqueued as we traverse. When the first leaf node is encountered (a node without left and right children), the current depth is returned as the minimum depth of the tree.
C++
Java
Python
C#
JavaScript
Time complexity is O(N), where N is the number of nodes, because each node is processed once. Space complexity is O(N) due to the storage requirements of the queue in the worst case (a complete/filled tree).
In the DFS approach, we perform a pre-order traversal of the tree with recursive calls. The minimum depth is calculated by determining the shortest path from the root to any leaf node, where leaf nodes are identified as those without children.
This C solution employs a recursive DFS approach. It works by evaluating the minimum depth between left and right sub-trees for each node, adding 1 for the depth of the current node, and utilizing base conditions to handle null nodes.
C++
Java
Python
C#
JavaScript
Time complexity is O(N) as each node requires inspection to determine minimum depth. Space complexity can be O(N) in the case of skewed trees due to the recursive stack's depth, but typically O(log N) for balanced trees.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time complexity is O(N), where N is the number of nodes, because each node is processed once. Space complexity is O(N) due to the storage requirements of the queue in the worst case (a complete/filled tree). |
| Depth-First Search (DFS) Approach | Time complexity is O(N) as each node requires inspection to determine minimum depth. Space complexity can be O(N) in the case of skewed trees due to the recursive stack's depth, but typically O(log N) for balanced trees. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n) | O(w) | Best for finding the shortest path to a leaf because traversal stops at the first leaf node encountered |
| Depth-First Search (DFS) | O(n) | O(h) | Useful when recursion is preferred or when solving tree depth problems consistently using DFS patterns |
Maximum Depth of Binary Tree - 3 Solutions - Leetcode 104 - Python • NeetCode • 296,166 views views
Watch 9 more video solutions →Practice Minimum Depth of Binary Tree with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor