Minimum Depth of Binary Tree - Practice Coding Problems

Minimum Depth of Binary Tree - 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.

Input & Output

Example 1 — Basic Tree

$ Input: root = [3,9,20,null,null,15,7]

› Output: 2

💡 Note: The shortest path is from root 3 to leaf 9, which has depth 2 (3 → 9). The other leaves are at depth 3.

Example 2 — Single Node

$ Input: root = [2]

› Output: 1

💡 Note: The root is also a leaf node, so the minimum depth is 1.

Example 3 — Skewed Tree

$ Input: root = [2,null,3,null,4,null,5,null,6]

› Output: 5

💡 Note: This is a right-skewed tree where the only leaf is at depth 5: 2 → 3 → 4 → 5 → 6.

Constraints

The number of nodes in the tree is in the range [0, 10⁵].
-1000 ≤ Node.val ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with nodes at different depths

Find Paths

Identify all paths from root to leaf nodes

Return Minimum

Return the shortest path length

Key Takeaway

🎯 Key Insight: Use BFS to find the first leaf node encountered, which guarantees minimum depth

Asked in

G Google 35 a Amazon 28 M Microsoft 22 Apple 18

The key insight is that BFS finds the minimum depth by exploring level by level, returning immediately when the first leaf is found. The optimal approach uses Breadth-First Search for early termination. Time: O(n), Space: O(w) where w is the maximum width of the tree.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(n)	O(h)	Recursively explore all paths and find minimum
Breadth-First Search (BFS)	O(n)	O(w)	Level-order traversal to find first leaf node

Brute Force DFS — Algorithm Steps

Start from root with depth 1
Recursively explore left and right subtrees
Return minimum depth of both subtrees plus 1

Visualization

Tap to expand

Step-by-Step Walkthrough

Start at Root

Begin DFS traversal from root node

Explore All Paths

Recursively visit left and right subtrees

Compare Depths

Return minimum depth found among all paths

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int solution(struct TreeNode* root) {
    if (!root) return 0;
    
    if (!root->left && !root->right) return 1;
    
    if (!root->left) return solution(root->right) + 1;
    
    if (!root->right) return solution(root->left) + 1;
    
    int leftDepth = solution(root->left);
    int rightDepth = solution(root->right);
    
    return (leftDepth < rightDepth) ? leftDepth + 1 : rightDepth + 1;
}

int main() {
    // For simplicity, create a test case manually
    struct TreeNode* root = createNode(3);
    root->left = createNode(9);
    root->right = createNode(20);
    root->right->left = createNode(15);
    root->right->right = createNode(7);
    
    printf("%d\n", solution(root));
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Must visit every node in the tree to find all leaf nodes

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals height of tree

✓ Linear Space

89.2K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler