deepSWE.io

Minimum Depth of a Binary Tree

TreesBFS

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.

Example

Output: 2

Algorithm Explanation

We can solve this problem using a breadth-first search (BFS) approach. BFS is ideal here because it explores the tree level by level, so the first leaf we encounter will be at the minimum depth.

Algorithm Steps

Queue: We'll use a queue to perform a level-order traversal. We start by adding the root to the queue along with its depth (1).
Level Traversal: While the queue is not empty, we dequeue a node and its depth.
Check for Leaf: If the dequeued node is a leaf (i.e., it has no children), we've found the shortest path, so we can return its depth.
Enqueue Children: If the node is not a leaf, we enqueue its left and right children with an incremented depth.

Start

Adding root to the queue.

Queue

(3, 1)

Minimum Depth of a Binary Tree Solution


from collections import deque

class Solution:
    def minDepth(self, root: Optional[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))