What is the time complexity of Minimum Depth of Binary Tree?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Minimum Depth of Binary Tree?

This problem uses Tree, Depth-First Search, Breadth-First Search, Binary Tree. Understanding these concepts is essential for solving this Easy problem efficiently.

What are the key insights for solving Minimum Depth of Binary Tree?

The definition of a 'leaf node' as having *no children* is absolutely critical. Many common tree traversal patterns might treat a path ending at a `null` link as a 'depth', but for minimum depth, we must ensure the path terminates at a concrete node that *itself* has no further descendants. Special handling for nodes with *only one child* is essential. If a node has a left child but no right child, the minimum depth to a leaf *must* come from its left subtree. Blindly applying `1 + min(minDepth(left), minDepth(right))` without these checks would incorrectly count a path ending at a `null` branch as a 'leaf path' if one child is `null` and the other leads to a very deep subtree.

Which companies ask LeetCode 111. Minimum Depth of Binary Tree in interviews?

This problem is frequently asked at Adobe, Google, Meta, Uber.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Minimum Depth of Binary Tree - LeetCode 111 Solution

Minimum Depth of Binary Tree - Complete Solution Guide

Minimum Depth of Binary Tree is LeetCode problem 111, a Easy level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

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, 10 5 ] . -1000 <= Node.val <= 1000

Detailed Explanation

Finding the minimum depth of a binary tree might sound straightforward, but it has a specific nuance that differentiates it from finding the maximum depth. The core of this problem lies in understanding what constitutes a 'leaf node' for the purpose of path termination. We're looking for the shortest path from the root down to any node that has no children at all. This means a node with only a left child (and no right) is *not* a leaf, and neither is a node with only a right child (and no left). The path must continue through that single child until an actual leaf is encountered. Consider Example 1: `root = [3,9,20,null,null,15,7]`. Here, node `9` is a leaf (no children), and its path from root `3` is `3 -> 9`, making a depth of 2. Nodes `15` and `7` are also leaves, but their paths `3 -> 20 -> 15` and `3 -> 20 -> 7` are both of length 3. Thus, the minimum depth is 2. If node `9` had, say, a left child, it wouldn't be a leaf, and we'd have to explore deeper. This strict 'no children' definition for a leaf node is the central point to grasp.

Solution Approach

The provided solution elegantly tackles this problem using a recursive Depth-First Search (DFS) pattern, carefully handling the edge cases that arise from the 'leaf node' definition. It works by asking each node to report the minimum depth to a leaf within its subtree. At its core, the logic is: if a node is empty (`null`), its depth is 0. If a node *is* a leaf (meaning it has no children), its depth is 1. The key trick comes when a node has *only one child*. If `root.left` is `null` but `root.right` exists, we *must* take the path through `root.right` because there's no leaf in the left subtree to terminate a path. Simply taking `min(depth(left), depth(right))` would incorrectly return `1` if `left` was `null` and `right` led to a deep subtree. Thus, if only one child exists, we recurse into that single child and add 1. Finally, if both children exist, we correctly take the minimum of the depths returned by the left and right subtrees, adding 1 for the current node. This specific branching logic ensures that we always follow a path that can eventually reach a *true* leaf node.

Step-by-Step Algorithm

Step 1: Check if the root is null. If so, return 0 (empty tree).
Step 2: Check if the root is a leaf node (no left and no right child). If so, return 1 (depth of a single node).
Step 3: If only the left subtree exists, recursively calculate the minimum depth of the left subtree and add 1.
Step 4: If only the right subtree exists, recursively calculate the minimum depth of the right subtree and add 1.
Step 5: If both left and right subtrees exist, recursively calculate the minimum depth of both subtrees, take the minimum, and add 1.

Key Insights

The definition of a 'leaf node' as having *no children* is absolutely critical. Many common tree traversal patterns might treat a path ending at a `null` link as a 'depth', but for minimum depth, we must ensure the path terminates at a concrete node that *itself* has no further descendants.
Special handling for nodes with *only one child* is essential. If a node has a left child but no right child, the minimum depth to a leaf *must* come from its left subtree. Blindly applying `1 + min(minDepth(left), minDepth(right))` without these checks would incorrectly count a path ending at a `null` branch as a 'leaf path' if one child is `null` and the other leads to a very deep subtree.
The recursive structure allows us to build the minimum depth from the bottom up. Each recursive call effectively solves the 'minimum depth' problem for its subtree, and by combining these results with specific rules for single-child nodes and true leaves, the overall minimum path is accurately determined.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(h)

Topics

This problem involves: Tree, Depth-First Search, Breadth-First Search, Binary Tree.

Companies

Asked at: Adobe, Google, Meta, Uber.

Minimum Depth of Binary Tree | LeetCode 111

Easy

Tree Depth-First Search Breadth-First Search Binary Tree

Time: O(n)Space: O(h)

Solution Code

Available in:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return 1;
        }
        int min_depth = Integer.MAX_VALUE;
        if (root.left != null) {
            min_depth = Math.min(minDepth(root.left), min_depth);
        }
        if (root.right != null) {
            min_depth = Math.min(minDepth(root.right), min_depth);
        }
        return min_depth + 1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 111: Minimum Depth of Binary Tree - Detailed explanation and solution approaches.

Topics

Tree Depth-First Search Breadth-First Search Binary Tree

Companies

AdobeGoogleMetaUber

Stats

Difficulty:Easy

Languages:4

Companies:4

Problem #:111

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Check if the root is null. If so, return 0 (empty tree).
2
Step 2: Check if the root is a leaf node (no left and no right child). If so, return 1 (depth of a single node).
3
Step 3: If only the left subtree exists, recursively calculate the minimum depth of the left subtree and add 1.
4
Step 4: If only the right subtree exists, recursively calculate the minimum depth of the right subtree and add 1.
5
Step 5: If both left and right subtrees exist, recursively calculate the minimum depth of both subtrees, take the minimum, and add 1.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(h)

📝

Why?

Each node is visited at most once in the DFS traversal. The space complexity is dominated by the depth of the recursive call stack, which is proportional to the height of the tree.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Breadth-First Search (BFS)

Use a queue to perform a level-order traversal. The first leaf node encountered determines the minimum depth.

Time: O(n)Space: O(w), where w is the maximum width of the tree. In a balanced tree, w is proportional to n, and in a skewed tree, w is a constant.

Trade-offs: BFS might be slightly more efficient in terms of space for balanced trees, and avoids deep recursion. DFS is generally easier to implement recursively.

✨

Key Insights

1The definition of a 'leaf node' as having *no children* is absolutely critical. Many common tree traversal patterns might treat a path ending at a `null` link as a 'depth', but for minimum depth, we must ensure the path terminates at a concrete node that *itself* has no further descendants.
2Special handling for nodes with *only one child* is essential. If a node has a left child but no right child, the minimum depth to a leaf *must* come from its left subtree. Blindly applying `1 + min(minDepth(left), minDepth(right))` without these checks would incorrectly count a path ending at a `null` branch as a 'leaf path' if one child is `null` and the other leads to a very deep subtree.
3The recursive structure allows us to build the minimum depth from the bottom up. Each recursive call effectively solves the 'minimum depth' problem for its subtree, and by combining these results with specific rules for single-child nodes and true leaves, the overall minimum path is accurately determined.

📚

Key Terms Explained

For Students

Tree

Hierarchical structure with nodes. Like a family tree!

Edge Cases

Edge case 1: Empty tree (root == null). The solution correctly handles this by returning 0.
Edge case 2: Tree with only one node (root only). The solution correctly handles this by returning 1.
Edge case 3: A tree where one subtree is empty. The solution correctly computes the depth based on the non-empty subtree.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Incorrectly handling the base case of an empty tree or a tree with only one node.

✗Common mistake 2: Not considering the possibility of one subtree being empty. The solution needs to handle cases where only one child node exists from a given parent.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Finding the shortest path in a hierarchical structure, such as an organizational chart or a file system directory structure.

🏦Real-world scenario 2: Determining the minimum number of levels in a decision tree used in machine learning or game AI.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

Most tree problems can be solved recursively. The base case is usually a null node. Think about what information needs to flow up vs down the tree.

🎯 Interview Tip

Even for easy problems, discuss time and space complexity. Interviewers want to see you think analytically.

⚠️ Watch Out

Not handling null nodes properly. Always check if the current node exists before accessing its children.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: September 20, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJun 29

❓

Frequently Asked Questions

What is the difference between DFS and BFS for trees?

DFS (using recursion or stack) explores depth-first, useful for path-finding and backtracking problems. BFS (using queue) explores level-by-level, ideal for finding shortest paths or processing nodes by depth. Choose based on whether level information matters.

What should I learn from easy problems?

Easy problems introduce core patterns that appear in harder problems. Master basic operations (iteration, conditionals, simple data structures), recognize common patterns (counting, searching, basic transformations), and practice explaining your thought process clearly.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Minimum Depth of Binary Tree"?

For this easy-level Tree problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?