Domain 1EasyCORE

Minimum Depth of Binary Tree

The problem requires finding the minimum depth of a binary tree. The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is one that has no children.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Tree#Depth-first Search#Breadth-first Search

111. Minimum Depth of Binary Tree

Model: qwen2.5-coder:14b
Topics: Tree,Depth-first Search,Breadth-first Search
FAANG asked: 1
Acceptance rate: 39.8%


Problem Breakdown

The problem requires finding the minimum depth of a binary tree. The minimum depth is defined as the number of nodes along the shortest path from the root node down to the nearest leaf node. A leaf node is one that has no children.

Inputs:

  • root: The root node of the binary tree.

Outputs:

  • An integer representing the minimum depth of the binary tree.

Implicit Constraints or Tricky Edge Cases:

  1. Empty Tree: If the input tree is empty (root is None), the minimum depth should be 0.
  2. Single Node Tree: A tree with only one node (the root) has a minimum depth of 1.
  3. Unbalanced Trees: The tree might be unbalanced, meaning one subtree could be significantly deeper than the other.

Intuition

A brute-force approach would involve traversing all paths from the root to leaf nodes and keeping track of the shortest path length. This approach is inefficient because it explores all possible paths, leading to a time complexity of O(n), where n is the number of nodes in the tree.

The key insight is that we can optimize this by using a breadth-first search (BFS) strategy. BFS naturally finds the shortest path in an unweighted graph or tree structure, as it explores nodes level by level. This approach ensures that we find the minimum depth more efficiently.

Approach

  1. Check for Empty Tree: If the root is None, return 0 immediately.
  2. Initialize Queue: Use a queue to facilitate BFS. Each element in the queue will be a tuple containing a node and its current depth.
  3. Breadth-First Search:
    • Start by adding the root node with an initial depth of 1 to the queue.
    • While the queue is not empty, process each node:
      • Dequeue the front element to get the current node and its depth.
      • If the current node is a leaf (i.e., it has no left or right children), return the current depth as this is the minimum depth.
      • Otherwise, enqueue the left child with an incremented depth if it exists.
      • Enqueue the right child with an incremented depth if it exists.
  4. Return Result: The function will return when a leaf node is encountered, ensuring that the minimum depth is found.

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the tree. This is because each node is visited once.
  • Space Complexity: O(n) in the worst case, where the queue contains all nodes at one level (e.g., a complete binary tree). In the best case, it’s O(1) if the tree is empty.

Solution

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def minDepth(root: TreeNode) -> int:
    if not root:
        return 0
    
    queue = deque([(root, 1)])
    
    while queue:
        node, depth = queue.popleft()
        
        # Check if it's a leaf node
        if not node.left and not node.right:
            return depth
        
        # Add children to the queue with incremented depth
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))

Edge Cases Handled

  • Empty Tree: The function returns 0 immediately if the root is None.
  • Single Node Tree: The root itself is a leaf, so the function returns 1.
  • Unbalanced Trees: BFS ensures that the shortest path to a leaf is found efficiently.