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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Depth of Binary Tree

Difficulty: Easy

Problem Description

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. A leaf is a node with no children.

Key Insights

  • The minimum depth is defined as the shortest distance from the root to the nearest leaf node.
  • A leaf node is a node that has no children.
  • The solution can be approached using either Depth-First Search (DFS) or Breadth-First Search (BFS).
  • BFS is particularly effective for this problem as it explores all nodes at the present depth level before moving on to nodes at the next depth level, ensuring that the first leaf node encountered will provide the minimum depth.

Space and Time Complexity

Time Complexity: O(N) - where N is the number of nodes in the tree, as we may need to visit every node. Space Complexity: O(H) - where H is the height of the tree, which represents the maximum depth of the recursion stack in DFS or the queue size in BFS.

Solution

To solve the problem, we can utilize either a DFS or a BFS approach. In DFS, we recursively explore each branch of the tree while keeping track of the depth. In contrast, a BFS approach uses a queue to explore nodes level by level, allowing us to find the minimum depth as soon as we reach the first leaf node.

Data Structure(s) Used:

  • Queue for BFS approach.
  • Recursion stack for DFS approach.

Algorithmic Approach:

  1. BFS: Start at the root node and add it to a queue. Iterate through the queue, exploring each node and their children. When a leaf node is encountered, return the current depth as it represents the minimum depth.
  2. DFS: Recursively traverse the tree. If a node is a leaf, return the depth. If it has only one child, continue down the existing path. Finally, choose the minimum depth from both children.

Code Solutions

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):
    if not root:
        return 0
    
    queue = deque([(root, 1)])  # Node and its depth
    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
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))
← Back to All Questions