We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Depth of Binary Tree

Number: 111

Difficulty: Easy

Paid? No

Companies: Google, Meta, Bloomberg, Amazon, Microsoft

Problem Description

Given a binary tree, determine its minimum depth, where 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 is a node with no children.

Key Insights

  • The shortest path to a leaf can be found using Breadth-First Search (BFS) because BFS explores nodes level by level.
  • Depth-First Search (DFS) can also be used recursively, but it might end up exploring more nodes than necessary.
  • When a node is found to be a leaf, the current depth is the answer.
  • Special edge case: An empty tree should return a depth of 0.

Space and Time Complexity

Time Complexity: O(N), where N is the number of nodes in the tree, because in the worst case every node is visited. Space Complexity: O(N) in the worst case when the tree is completely unbalanced (or the queue/stack holds all nodes at the deepest level during traversal).

Solution

The approach uses Breadth-First Search (BFS) to find the minimum depth. We start at the root and traverse level by level. As soon as we encounter a leaf (a node with no left or right children), we return the current depth. This guarantees that we return the shortest path from the root to a leaf. The main data structure used is a queue to facilitate level order traversal.

Code Solutions

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val  # Node's value
        self.left = left  # Left child
        self.right = right  # Right child

from collections import deque

def minDepth(root: TreeNode) -> int:
    # If the tree is empty, return depth as 0
    if not root:
        return 0

    # Initialize queue for BFS with tuple (node, current depth)
    queue = deque([(root, 1)])
    
    while queue:
        current, depth = queue.popleft()  # Get current node and its depth
        # If current is a leaf node, we've found the minimum depth
        if not current.left and not current.right:
            return depth
        # If left child exists, add it to the queue with incremented depth
        if current.left:
            queue.append((current.left, depth + 1))
        # If right child exists, add it to the queue with incremented depth
        if current.right:
            queue.append((current.right, depth + 1))
    
    # Should never be reached if tree is not empty
    return 0
← Back to All Questions