Minimum Depth of Binary Tree solution and explanation
TCS
Google
9 more videos on this problem
Minimum Depth of Binary Tree (LeetCode 111) | Full solution w/ graphical examples | Study AlgorithmsNikhil Lohia · 11:50 · 14K views
MINIMUM DEPTH OF BINARY TREE | LEETCODE # 111 | PYTHON DFS SOLUTIONCracking FAANG · 8:03 · 12K views
Minimum Depth of Binary Tree, Do you do these mistakes in an interview ? LeetCode - 111, 104InterviewDose · 5:11 · 8K views
Minimum Depth of Binary Tree | LeetCode 111 | Coding Interview TutorialTerrible Whiteboard · 12:34 · 6K views
Leetcode - Minimum Depth of Binary Tree (Python)Timothy H Chang · 4:31 · 5K views
LeetCode Tutorial 111. Minimum Depth of Binary TreeGoodTecher · 8:00 · 4K views
Minimum Depth of Binary Tree - LeetCode 111 - JavaScriptAlgoJS · 4:59 · 1K views
Leetcode 111. Minimum Depth of Binary TreeJeevan Kumar - Cracckify · 5:55 · 1K views
Leetcode 111. Minimum Depth of Binary Tree (Python)Pseudocoder Ravina · 10:48 · 1K views
Minimum Depth of Binary Tree - Leetcode 111 - JavaMastering Programming · 5:31 · 935 views
The 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.
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.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
queue = deque([(root, 1)])
while queue:
node, depth = queue.popleft()
if not node.left and not node.right:
return depth
if node.left:
queue.append((node.left, depth + 1))
if node.right:
queue.append((node.right, depth + 1))
return 0import java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left, right;
TreeNode (int x) {
val = x;
left = right = null;
}
}
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int depth = 1;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
if (node.left == null && node.right == null) return depth;
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
depth++;
}
return 0;
}
}#include <iostream>
#include <queue>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int minDepth(TreeNode* root) {
if (!root) return 0;
queue<pair<TreeNode*, int>> q;
q.push({root, 1});
while (!q.empty()) {
TreeNode* node = q.front().first;
int depth = q.front().second;
q.pop();
if (!node->left && !node->right) return depth;
if (node->left) q.push({node->left, depth + 1});
if (node->right) q.push({node->right, depth + 1});
}
return 0;
}function TreeNode(val, left=null, right=null) {
this.val = (val===undefined ? 0 : val);
this.left = (left===undefined ? null : left);
this.right = (right===undefined ? null : right);
}
var minDepth = function(root) {
if (root === null) return 0;
const queue = [[root, 1]];
while (queue.length) {
const [node, depth] = queue.shift();
if (node.left === null && node.right === null) {
return depth;
}
if (node.left !== null) {
queue.push([node.left, depth + 1]);
}
if (node.right !== null) {
queue.push([node.right, depth + 1]);
}
}
return 0;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct QueueNode {
struct TreeNode *node;
int depth;
struct QueueNode *next;
};
void enqueue(struct QueueNode **head, struct TreeNode *node, int depth) {
struct QueueNode *newNode = (struct QueueNode *)malloc(sizeof(struct QueueNode));
newNode->node = node;
newNode->depth = depth;
newNode->next = NULL;
if (*head == NULL) {
*head = newNode;
} else {
struct QueueNode *temp = *head;
while (temp->next) {
temp = temp->next;
}
temp->next = newNode;
}
}
struct QueueNode *dequeue(struct QueueNode **head) {
struct QueueNode *temp = *head;
if (*head) {
*head = (*head)->next;
}
return temp;
}
int minDepth(struct TreeNode *root) {
if (root == NULL) return 0;
struct QueueNode *queue = NULL;
enqueue(&queue, root, 1);
while (queue != NULL) {
struct QueueNode *current = dequeue(&queue);
struct TreeNode *node = current->node;
int depth = current->depth;
if (!node->left && !node->right) {
return depth;
}
if (node->left) enqueue(&queue, node->left, depth + 1);
if (node->right) enqueue(&queue, node->right, depth + 1);
free(current);
}
return 0;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MinDepth(TreeNode root) {
if (root == null) return 0;
Queue<(TreeNode, int)> queue = new Queue<(TreeNode, int)>();
queue.Enqueue((root, 1));
while (queue.Count > 0) {
var (node, depth) = queue.Dequeue();
if (node.left == null && node.right == null) return depth;
if (node.left != null) queue.Enqueue((node.left, depth + 1));
if (node.right != null) queue.Enqueue((node.right, depth + 1));
}
return 0;
}
}This Python solution implements BFS using a deque from the collections module, allowing efficient append and pop operations. The BFS processes each level in sequence, updating the depth. The loop breaks and returns the minimum depth when a leaf node is encountered.
Time complexity is O(N) as each node enters and exits the queue once. Space complexity is O(N), as the queue could contain all nodes at once in perfectly balanced scenarios.
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.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root:
return 0
if not root.left:
return 1 + self.minDepth(root.right)
if not root.right:
return 1 + self.minDepth(root.left)
return 1 + min(self.minDepth(root.left), self.minDepth(root.right))class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public int minDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int left = (root.left != null) ? minDepth(root.left) : Integer.MAX_VALUE;
int right = (root.right != null) ? minDepth(root.right) : Integer.MAX_VALUE;
return 1 + Math.min(left, right);
}
}#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
int minDepth(TreeNode* root) {
if (root == nullptr) return 0;
if (!root->left && !root->right) return 1;
int left = root->left ? minDepth(root->left) : INT_MAX;
int right = root->right ? minDepth(root->right) : INT_MAX;
return 1 + min(left, right);
}function TreeNode(val, left, right) {
this.val = (val===undefined ? 0 : val)
this.left = (left===undefined ? null : left)
this.right = (right===undefined ? null : right)
}
var minDepth = function(root) {
if (!root) return 0;
if (!root.left) return 1 + minDepth(root.right);
if (!root.right) return 1 + minDepth(root.left);
return 1 + Math.min(minDepth(root.left), minDepth(root.right));
};#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int minDepth(struct TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
if (!root->left) return 1 + minDepth(root->right);
if (!root->right) return 1 + minDepth(root->left);
return 1 + (minDepth(root->left) < minDepth(root->right) ? minDepth(root->left) : minDepth(root->right));
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public int MinDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int left = root.left != null ? MinDepth(root.left) : int.MaxValue;
int right = root.right != null ? MinDepth(root.right) : int.MaxValue;
return 1 + Math.Min(left, right);
}
}The recursive Python solution explores the minimum depth by traversing each sub-tree, employing the function's call stack to differentiate paths and returning the shortest discovered path to a leaf.
Time complexity is O(N), owing to examining every node. Space complexity is O(N) in a worst-case scenario due to the recursion stack's growth.
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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
if (root == null) {
return 0;
}
const { left, right } = root;
if (left == null) {
return 1 + minDepth(right);
}
if (right == null) {
return 1 + minDepth(left);
}
return 1 + Math.min(minDepth(left), minDepth(right));
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) int {
if root == nil {
return 0
}
if root.Left == nil {
return 1 + minDepth(root.Right)
}
if root.Right == nil {
return 1 + minDepth(root.Left)
}
return 1 + min(minDepth(root.Left), minDepth(root.Right))
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
fn dfs(root: &Option<Rc<RefCell<TreeNode>>>) -> i32 {
if root.is_none() {
return 0;
}
let node = root.as_ref().unwrap().borrow();
if node.left.is_none() {
return 1 + Self::dfs(&node.right);
}
if node.right.is_none() {
return 1 + Self::dfs(&node.left);
}
1 + Self::dfs(&node.left).min(Self::dfs(&node.right))
}
pub fn min_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
Self::dfs(&root)
}
}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.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function minDepth(root: TreeNode | null): number {
if (!root) {
return 0;
}
const q = [root];
let ans = 0;
while (1) {
++ans;
for (let n = q.length; n; --n) {
const node = q.shift();
if (!node.left && !node.right) {
return ans;
}
if (node.left) {
q.push(node.left);
}
if (node.right) {
q.push(node.right);
}
}
}
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDepth(root *TreeNode) (ans int) {
if root == nil {
return 0
}
q := []*TreeNode{root}
for {
ans++
for n := len(q); n > 0; n-- {
node := q[0]
q = q[1:]
if node.Left == nil && node.Right == nil {
return
}
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time complexity is O(N) as each node enters and exits the queue once. Space complexity is O(N), as the queue could contain all nodes at once in perfectly balanced scenarios. |
| Depth-First Search (DFS) Approach | Time complexity is O(N), owing to examining every node. Space complexity is O(N) in a worst-case scenario due to the recursion stack's growth. |
| Recursion | – |
| BFS | – |
Complexity analysis
| 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 |
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.