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: Given the root of a binary tree, return the 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).
Approach 1: Breadth-First Search (BFS) (Time: O(n), Space: O(n))
Breadth-first search processes the tree level by level using a queue. Start by pushing the root node with depth 1 into the queue. At each step, pop the front node, check if it is a leaf (both left and right children are null), and return the current depth immediately. Because BFS explores nodes level-wise, the first leaf encountered is guaranteed to be the minimum depth. This approach is often preferred because it stops early without traversing the entire tree in many cases.
The algorithm repeatedly performs enqueue operations for left and right children while tracking the depth for each node. In the worst case you visit every node once, giving O(n) time complexity. The queue can hold up to one full level of the tree, leading to O(n) space in a wide tree. This approach relies on standard Breadth-First Search traversal on a Binary Tree.
Approach 2: Depth-First Search (DFS) (Time: O(n), Space: O(h))
Depth-first search explores each path from root to leaf using recursion or an explicit stack. Recursively compute the minimum depth of the left and right subtrees, then return 1 + min(leftDepth, rightDepth). The tricky part is handling nodes that have only one child. If one subtree is null, you must continue through the non-null subtree instead of taking the minimum with zero.
DFS visits every node once, resulting in O(n) time complexity. The recursion stack depth equals the tree height h, which leads to O(h) space. In a balanced tree this is O(log n), but in a skewed tree it can reach O(n). This method uses classic Depth-First Search traversal and is easy to implement recursively.
Recommended for interviews: BFS is usually the expected approach because it naturally finds the closest leaf first and avoids unnecessary traversal. Interviewers like it because it demonstrates understanding of level-order traversal and early termination. Showing the DFS solution still helps demonstrate strong recursion fundamentals and a solid grasp of binary tree edge cases.
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.
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.
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.
The termination condition for recursion is when the current node is null, at which point return 0. If one of the left or right subtrees of the current node is null, return the minimum depth of the non-null subtree plus 1. If neither the left nor right subtree of the current node is null, return the smaller value of the minimum depths of the left and right subtrees plus 1.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C
Use a queue to implement breadth-first search, initially adding the root node to the queue. Each time, take a node from the queue. If this node is a leaf node, directly return the current depth. If this node is not a leaf node, add all non-null child nodes of this node to the queue. Continue to search the next layer of nodes until a leaf node is found.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary tree.
Python
Java
C++
Go
TypeScript
JavaScript
| 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. |
| Recursion | — |
| BFS | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (BFS) | O(n) | O(n) | Best when you want the shortest path to the nearest leaf quickly; stops early once the first leaf is found |
| Depth-First Search (DFS) | O(n) | O(h) | Good for recursive implementations or when performing other subtree calculations during traversal |
Minimum Depth of Binary Tree (LeetCode 111) | Full solution w/ graphical examples | Study Algorithms • Nikhil Lohia • 13,425 views views
Watch 9 more video solutions →Practice Minimum Depth of Binary Tree with our built-in code editor and test cases.
Practice on FleetCode