Skip to main content
Talentd

Minimum Depth of Binary Tree - Solution & Explanation

EasyTreeDepth-First SearchBreadth-First SearchBinary Tree26 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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:

  • The number of nodes in the tree is in the range [0, 105].
  • -1000 <= Node.val <= 1000

Approach Overview

Problem 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.

Approach 1: Breadth-First Search (BFS) Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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).

Try this approach in the editor →

Approach 2: Depth-First Search (DFS) Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Recursion

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.

Code

PythonJavaC++GoTypeScriptRustJavaScriptC

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C

Try this approach in the editor →

Approach 4: BFS

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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

Video Solution

Minimum Depth of Binary Tree (LeetCode 111) | Full solution w/ graphical examples | Study Algorithms • Nikhil Lohia • 14,737 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Depth of Binary Tree easy or hard?
Minimum Depth of Binary Tree is classified as an Easy problem on most coding platforms. The challenge mainly involves recognizing that BFS naturally finds the nearest leaf and correctly handling edge cases when using DFS with nodes that have only one child.
Minimum Depth of Binary Tree Python/Java solution
Python and Java solutions typically implement either BFS using a queue or DFS using recursion. The BFS version uses a queue to track nodes and their depth, returning immediately when the first leaf is found. Both implementations run in O(n) time and are widely accepted in coding interviews and online judges.
How to solve Minimum Depth of Binary Tree in O(n)?
Traverse the tree once using either BFS or DFS. In BFS, push the root into a queue and process nodes level by level until you encounter the first leaf node, then return the depth. In DFS, recursively compute the depth of left and right subtrees while carefully handling nodes with only one child. Both strategies visit each node once, resulting in O(n) time complexity.
What is the best approach for Minimum Depth of Binary Tree?
Breadth-first search (BFS) is generally the best approach. BFS traverses the tree level by level, so the first leaf node encountered is guaranteed to represent the minimum depth. This allows early termination without exploring deeper levels. The time complexity is O(n) and the space complexity is O(n) in the worst case.
Is Minimum Depth of Binary Tree asked at Google/Amazon/Meta?
Minimum depth and other binary tree traversal problems appear frequently in interviews at companies such as Amazon, Google, and Meta. Interviewers use it to test understanding of tree traversal strategies, recursion, and BFS level-order processing. Variations of tree depth problems are common in coding rounds.
What data structure is used in Minimum Depth of Binary Tree?
The primary data structure is a binary tree. The BFS solution additionally uses a queue to process nodes level by level, while the DFS solution uses recursion or an explicit stack. Both approaches rely on tree traversal techniques.
What is the time complexity of Minimum Depth of Binary Tree?
The time complexity is O(n) because every node may need to be visited once in the worst case. Both BFS and DFS solutions traverse the tree nodes exactly once. The difference lies in space usage: BFS may use O(n) queue space while DFS typically uses O(h) recursion stack space.

Ready to solve this problem?

Practice Minimum Depth of Binary Tree with our built-in code editor and test cases.

Practice on FleetCode
Previous

Binary Tree Level Order Traversal

Next

Maximum Depth of Binary Tree