[Solved] The following BFS-based code attempts to compute the maximum depth of a binary tree.... Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input. | Tree: Depth-First Search

Tree: Depth-First Search - Maximum Depth of Binary Tree

The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.

from collections import deque

def maxDepth(root):
    queue = deque([root])
    depth = 0
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        depth += 1
    return depth

ALine 7: Using len(queue) to determine level size

BLine 15: Incrementing depth after processing each level

CLine 10: Popping node from queue without null check

DLine 2: Initializing queue with root without checking if root is null

Step-by-Step Solution

Solution:

Step 1: Check handling of empty tree
Code initializes queue with root without checking if root is null, so if root is null, queue contains null, causing errors.
Step 2: Verify other lines
len(queue) and popping nodes are correct if queue is valid; depth increment is necessary after each level.
Final Answer:
Option D -> Option D
Quick Check:
Missing root null check causes failure on empty tree [OK]

Quick Trick: Always check for null root before queue initialization [OK]

Common Mistakes:

MISTAKES

Not handling empty tree input
Assuming root always exists
Incrementing depth incorrectly

Trap Explanation:

PITFALL

Code looks correct but fails on empty input due to missing root check.

Interviewer Note:

CONTEXT

Tests attention to edge cases and null input handling.

Master "Maximum Depth of Binary Tree" in Tree: Depth-First Search

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Tree: Depth-First Search Quizzes

The following BFS-based code attempts to compute the maximum depth of a binary tree. Identify the line containing the subtle bug that causes incorrect depth calculation for an empty tree input.

Step 1: Check handling of empty tree

Step 2: Verify other lines

Final Answer:

Quick Check:

Want More Practice?