Minimum Depth of Binary Tree

▶

Steps

setup

Check if root is null

The algorithm checks if the root node is null. Since the root exists, it proceeds to initialize the queue.

💡 This step handles the edge case of an empty tree, which would have a minimum depth of 0.

Line:

if not root:
    return 0

💡 The algorithm only proceeds if there is a tree to traverse.

setup

Initialize queue with root node at depth 1

The queue is initialized with the root node (value 3) paired with depth 1, marking the start of BFS traversal.

💡 Starting BFS requires a queue to track nodes and their depths level by level.

Line:

queue = deque([(root, 1)])

💡 The root node is the first node to be processed, at depth 1.

traverse

Dequeue root node and check if leaf

The root node (3) is dequeued from the queue. The algorithm checks if it is a leaf node (no children).

💡 Checking if the current node is a leaf determines if we can return the minimum depth immediately.

Line:

node, depth = queue.popleft()
if not node.left and not node.right:

💡 Since node 3 is not a leaf, BFS continues to explore its children.

fill_cells

Enqueue left child (9) at depth 2

Since node 3 has a left child (9), it is enqueued with depth incremented by 1 (depth 2).

💡 Adding children to the queue ensures BFS explores nodes level by level.

Line:

if node.left:
    queue.append((node.left, depth + 1))

💡 The queue now contains node 9 at depth 2, the next node to check for leaf status.

fill_cells

Enqueue right child (20) at depth 2

Node 3's right child (20) is also enqueued with depth 2, to be processed after node 9.

💡 Both children of a node are enqueued to ensure BFS covers all nodes at the current depth before moving deeper.

Line:

if node.right:
    queue.append((node.right, depth + 1))

💡 The queue now contains nodes 9 and 20 at depth 2, preserving BFS order.

traverse

Dequeue node 9 and check if leaf

Node 9 is dequeued from the queue and checked if it is a leaf node (no children).

💡 Finding a leaf node means we have found the minimum depth, so BFS can stop.

Line:

node, depth = queue.popleft()
if not node.left and not node.right:

💡 The first leaf found by BFS determines the minimum depth of the tree.

returning

Return minimum depth 2

Since node 9 is a leaf, the algorithm returns its depth (2) as the minimum depth of the tree.

💡 Returning immediately upon finding the first leaf ensures BFS is optimal for minimum depth.

Line:

if not node.left and not node.right:
    return depth

💡 BFS guarantees this is the shortest path to a leaf.

traverse

Dequeue node 20 for completeness

Although the algorithm has returned, we show the next node (20) dequeued to illustrate BFS order if it continued.

💡 This step is for educational purposes to show BFS order beyond the minimum depth leaf.

Line:

node, depth = queue.popleft()

💡 BFS processes nodes level by level; node 20 is next after node 9 at depth 2.

fill_cells

Enqueue left child (15) of node 20

Node 20's left child (15) would be enqueued at depth 3 if BFS continued.

💡 This shows how BFS would continue exploring deeper levels if needed.

Line:

if node.left:
    queue.append((node.left, depth + 1))

💡 BFS explores all nodes at current depth before moving deeper.

fill_cells

Enqueue right child (7) of node 20

Node 20's right child (7) would be enqueued at depth 3 if BFS continued.

💡 This completes the illustration of BFS exploring all children at the next level.

Line:

if node.right:
    queue.append((node.right, depth + 1))

💡 BFS ensures all nodes at a given depth are processed before going deeper.

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):
    # STEP 1: Check if root is null
    if not root:
        return 0
    # STEP 2: Initialize queue with root and depth 1
    queue = deque([(root, 1)])
    while queue:
        # STEP 3: Dequeue node and depth
        node, depth = queue.popleft()
        # STEP 6: Check if node is leaf
        if not node.left and not node.right:
            # STEP 7: Return depth if leaf
            return depth
        # STEP 4: Enqueue left child if exists
        if node.left:
            queue.append((node.left, depth + 1))
        # STEP 5: Enqueue right child if exists
        if node.right:
            queue.append((node.right, depth + 1))

if __name__ == '__main__':
    root = TreeNode(3)
    root.left = TreeNode(9)
    root.right = TreeNode(20, TreeNode(15), TreeNode(7))
    print(minDepth(root))  # Output: 2

📊

Minimum Depth of Binary Tree - Watch the Algorithm Execute, Step by Step

Watching this step-by-step BFS traversal helps you understand how the algorithm efficiently finds the shortest path to a leaf without exploring unnecessary nodes.

3920157

Current node: 1

3920157

DFS Stack

1 (entered)depth=1

Current node: 1

3920157

DFS Stack

1 (left_done)depth=1

Current node: 2

3920157

DFS Stack

2 (entered)depth=2

Current node: 2

3920157

DFS Stack

2 (entered)depth=2

Current node: 2

3920157

DFS Stack

2 (returning)depth=2

Return: 2

3920157

Return: 2

Current node: 3

3920157

DFS Stack

3 (entered)depth=2

Return: 2

Current node: 4

3920157

DFS Stack

4 (entered)depth=3

Return: 2

Current node: 5

3920157

DFS Stack

5 (entered)depth=3

Return: 2

Key Takeaways

✓ BFS finds the minimum depth by exploring nodes level by level and stopping at the first leaf.

This insight is hard to see from code alone because the early return on the first leaf is subtle but crucial for efficiency.

✓ The queue maintains nodes paired with their depth, enabling the algorithm to track how deep each node is in the tree.

Visualizing the queue contents clarifies how BFS progresses through the tree in order.

✓ The algorithm does not explore unnecessary nodes beyond the first leaf, demonstrating BFS's optimality for minimum depth problems.

Seeing the traversal stop early helps understand why BFS is preferred over DFS for this problem.

Practice

1. Given the following Python code for DFS-based level order traversal and the binary tree below, what is the final returned list? Tree structure: ``` 1 / \ 2 3 ```

from typing import List, Optional

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

def dfs_level_order(root: Optional[TreeNode]) -> List[List[int]]:
    result = []
    def dfs(node: Optional[TreeNode], level: int):
        if not node:
            return
        if level == len(result):
            result.append([])
        result[level].append(node.val)
        dfs(node.left, level + 1)
        dfs(node.right, level + 1)
    dfs(root, 0)
    return result

easy

A. [[1], [2, 3]]

B. [[1], [3, 2]]

C. [[1, 2, 3]]

D. [[2, 3], [1]]

Solution

1. Step 1: Trace dfs call for root node (val=1, level=0)

   Since level 0 equals result length 0, append new list: result = [[]]. Append 1 to result[0].

2. Step 2: Trace dfs call for left child (val=2, level=1)

   Level 1 equals result length 1, append new list: result = [[1], []]. Append 2 to result[1]. Then dfs on left and right children (null) returns immediately.

3. Step 3: Trace dfs call for right child (val=3, level=1)

   Level 1 already exists in result, append 3 to result[1].

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Nodes grouped by level: [[1], [2, 3]] [OK]

Hint: DFS with level tracking appends nodes in level order [OK]

Common Mistakes:

• Swapping left and right children order
• Appending all nodes to one list
• Miscounting levels

2. Given the following code for finding largest values in each tree row, what is the returned list when the input tree is: 1 / \ 3 2 / \ \ 5 3 9

from collections import deque
from typing import Optional, List

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

def largestValues(root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    res = []
    queue = deque([root])
    while queue:
        level_max = float('-inf')
        for _ in range(len(queue)):
            node = queue.popleft()
            level_max = max(level_max, node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        res.append(level_max)
    return res

easy

A. [1, 3, 5]

B. [1, 3, 9]

C. [1, 5, 9]

D. [1, 2, 9]

Solution

1. Step 1: Trace first level with root node value 1

   Queue initially contains [1]. Max is 1. Append 1 to result.

2. Step 2: Trace second level with nodes 3 and 2

   Queue now [3, 2]. Max is max(3, 2) = 3. Append 3 to result.

3. Step 3: Trace third level with nodes 5, 3, and 9

   Queue now [5, 3, 9]. Max is max(5, 3, 9) = 9. Append 9 to result.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Levels: [1], [3,2], [5,3,9] max values [1,3,9] [OK]

Hint: Track queue size per level to avoid mixing levels [OK]

Common Mistakes:

• Off-by-one in loop causing missing last level
• Mixing nodes from different levels in max calculation
• Incorrect initialization of level_max

3. Given the following code snippet implementing the optimal approach to connect next right pointers in a perfect binary tree, what is the value of root.left.next.val after calling connect(root) on the tree Node(1, Node(2), Node(3))?

easy

A. None

B. 2

C. 3

D. 1

Solution

1. Step 1: Trace the first iteration of the outer while loop

   leftmost is root (1), which has left child (2). Inside inner loop, head is 1, so 2.next = 3.

2. Step 2: Check the value of root.left.next

   root.left is node 2, its next pointer is set to node 3, so root.left.next.val = 3.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   2.next points to 3 after connect [OK]

Hint: Next pointer of left child points to right sibling [OK]

Common Mistakes:

• Confusing node values
• Assuming next is None by default
• Mixing up left and right children

4. Identify the bug in the following code snippet for the right side view of a binary tree:

def rightSideView(root: Optional[TreeNode]) -> List[int]:
    rightside = []
    def dfs(node, depth):
        if not node:
            return
        if depth == len(rightside):
            rightside.append(node.val)
        dfs(node.left, depth + 1)  # Line X
        dfs(node.right, depth + 1) # Line Y
    dfs(root, 0)
    return rightside

Which line contains the bug causing incorrect right side view?

medium

A. Line with 'if depth == len(rightside): rightside.append(node.val)'

B. Line X: 'dfs(node.left, depth + 1)'

C. Line Y: 'dfs(node.right, depth + 1)'

D. Line with 'if not node: return'

Solution

1. Step 1: Understand traversal order

   The code visits left child before right child, so left nodes are appended first at each depth.

2. Step 2: Why this causes bug

   Visiting left first causes left nodes to be recorded as visible, overwriting right nodes that should be visible from the right side.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Swapping left and right child calls fixes the bug [OK]

Hint: Right-first DFS needed to capture rightmost nodes [OK]

Common Mistakes:

• Visiting left child before right in DFS causes wrong nodes appended
• Appending nodes without checking depth length
• Not handling null nodes properly

5. Suppose you want to modify the bottom-up level order traversal to return only the k bottom-most levels of the tree. Which modification to the optimal DFS approach is correct and efficient?

hard

A. Use BFS and prepend each level to the result list, stopping after k levels are collected.

B. During DFS, keep track of maximum depth and prune traversal once depth exceeds k.

C. Modify DFS to insert each node's value at the front of its level list to avoid reversal.

D. Perform full DFS to collect all levels, then slice the last k levels from the reversed list before returning.

Solution

1. Step 1: Understand requirement to return only k bottom-most levels

   We must know total depth to identify bottom k levels.

2. Step 2: Evaluate options

   Only performing full DFS and then slicing the reversed levels guarantees correctness; pruning by depth is incorrect because bottom levels are deepest, not shallowest.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Full DFS then slicing is simple and correct [OK]

Hint: Bottom k levels require knowing total depth first [OK]

Common Mistakes:

• Pruning DFS early loses bottom levels
• Inserting at front of level list breaks order