The algorithm first checks if the root node is null. Since the root exists, it proceeds to initialize the queue.
💡 This step ensures we handle the edge case of an empty tree, which would have depth zero.
Line:if root is None:
return 0
💡 The algorithm only proceeds if there is at least one node to process.
setup
Initialize queue with root and depth counter
The root node (value 3) is enqueued to start BFS. The depth counter is initialized to zero.
💡 Starting BFS requires a queue with the root node and a depth counter to track levels.
Line:queue = deque([root])
depth = 0
💡 The queue now contains the first level (root only), and depth is ready to count levels.
fill_row
Start processing level 1
The algorithm begins processing the first level, which contains only the root node (3). The level size is recorded as 1.
💡 Knowing the number of nodes at the current level helps process exactly that many nodes before incrementing depth.
Line:while queue:
level_size = len(queue)
💡 The level size controls the loop that processes all nodes at this level.
fill_cells
Dequeue root node and enqueue its children
The root node (3) is dequeued and its children (9 and 20) are enqueued for the next level.
💡 Processing each node involves visiting it and adding its children to the queue for future processing.
Line:node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
💡 Children nodes are prepared for the next level's processing by adding them to the queue.
fill_row
Finish processing level 1 and increment depth
All nodes at level 1 have been processed, so the depth counter is incremented from 0 to 1.
💡 Depth increases after completing all nodes at the current level, reflecting the number of levels traversed.
Line:depth += 1
💡 Depth corresponds to the number of levels fully processed so far.
fill_row
Start processing level 2
The algorithm begins processing the second level, which contains nodes 9 and 20. The level size is 2.
💡 Processing all nodes at this level before incrementing depth ensures accurate depth counting.
Line:level_size = len(queue)
💡 Level size controls the number of nodes processed in this iteration.
fill_cells
Dequeue node 9 (no children)
Node 9 is dequeued and processed. It has no children, so nothing is enqueued.
💡 Leaf nodes do not add any new nodes to the queue, so the next level size depends on other nodes.
Line:node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
💡 Leaf nodes mark the end of a branch and do not increase depth further.
fill_cells
Dequeue node 20 and enqueue its children
Node 20 is dequeued and its children 15 and 7 are enqueued for the next level.
💡 Non-leaf nodes add their children to the queue, expanding the next level's nodes.
Line:node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
💡 The queue now contains all nodes at the next level to be processed.
fill_row
Finish processing level 2 and increment depth
All nodes at level 2 have been processed, so the depth counter increments from 1 to 2.
💡 Incrementing depth after processing all nodes at a level reflects the tree height so far.
Line:depth += 1
💡 Depth now counts two levels: root and its children.
fill_row
Start processing level 3
The algorithm begins processing the third level, which contains nodes 15 and 7. The level size is 2.
💡 Processing the last level nodes will complete the BFS traversal.
Line:level_size = len(queue)
💡 Level size controls the number of nodes processed at this deepest level.
fill_cells
Dequeue node 15 (no children)
Node 15 is dequeued and processed. It has no children, so nothing is enqueued.
💡 Leaf nodes at the deepest level do not add further nodes to the queue.
Line:node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
💡 Processing leaf nodes reduces the queue size without adding new nodes.
fill_cells
Dequeue node 7 (no children)
Node 7 is dequeued and processed. It has no children, so the queue becomes empty.
💡 Processing the last node empties the queue, signaling BFS completion.
Line:node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
💡 Empty queue means all nodes have been processed.
fill_row
Finish processing level 3 and increment depth
All nodes at level 3 have been processed, so the depth counter increments from 2 to 3.
💡 Incrementing depth after the last level reflects the maximum depth of the tree.
Line:depth += 1
💡 Depth now equals the height of the tree: 3.
reconstruct
Return the maximum depth
The BFS loop ends as the queue is empty. The algorithm returns the depth value 3 as the maximum depth of the tree.
💡 Returning the depth completes the algorithm and provides the final answer.
Line:return depth
💡 The maximum depth is the number of levels processed by BFS.
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 maxDepth(root):
# STEP 1: Check if root is None
if root is None:
return 0
# STEP 2: Initialize queue with root and depth counter
queue = deque([root])
depth = 0
# STEP 3: While queue not empty, process each level
while queue:
level_size = len(queue) # STEP 3
# STEP 4: Process all nodes at current level
for _ in range(level_size):
node = queue.popleft() # STEP 4
if node.left:
queue.append(node.left) # STEP 4
if node.right:
queue.append(node.right) # STEP 4
depth += 1 # STEP 5: Increment depth after level
return depth # STEP 6: Return final depth
if __name__ == '__main__':
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20, TreeNode(15), TreeNode(7))
print(maxDepth(root)) # Output: 3
📊
Maximum Depth of Binary Tree - Watch the Algorithm Execute, Step by Step
Watching the algorithm process each level of the tree visually helps you understand how BFS explores nodes layer by layer and how depth is measured by counting these layers.
Step 1/14
·Active fill★Answer cell
3920157
3920157
BFS Queue
N0 (L0)
Current node: 0
3920157
BFS Queue
N0 (L0)
3920157
BFS Queue
N1 (L1)N2 (L1)
3920157
BFS Queue
N1 (L1)N2 (L1)
Current node: 1
3920157
BFS Queue
N1 (L1)N2 (L1)
3920157
BFS Queue
N2 (L1)
3920157
BFS Queue
N3 (L2)N4 (L2)
3920157
BFS Queue
N3 (L2)N4 (L2)
Current node: 3
3920157
BFS Queue
N3 (L2)N4 (L2)
3920157
BFS Queue
N4 (L2)
3920157
3920157
3920157
Return: 3
Key Takeaways
✓ Maximum depth corresponds to the number of levels processed in BFS.
This insight is hard to see from code alone because depth is incremented outside the inner loop, which might be overlooked without visualization.
✓ BFS processes nodes level by level, enqueuing children to prepare the next level.
Visualizing the queue contents at each step clarifies how BFS expands the frontier and separates levels.
✓ Leaf nodes do not add children to the queue, signaling the end of branches.
Seeing leaf nodes removed from the queue without enqueuing new nodes helps understand how BFS naturally terminates.
Practice
(1/5)
1. Given the following code for the optimal camera placement, what is the final number of cameras placed for the tree with root node 0, left child 1, and right child 2 (both children are leaves)?
easy
A. 2
B. 0
C. 3
D. 1
Solution
Step 1: Trace dfs on leaf nodes 1 and 2
Leaves return NOT_COVERED (0) because their children are null and return COVERED_NO_CAM (1). So dfs(1) and dfs(2) return NOT_COVERED.
Step 2: At root node 0, left or right child is NOT_COVERED, so place a camera here
Increment cameras to 1 and return HAS_CAM (2). The root is covered, so no extra camera needed.
Final Answer:
Option D -> Option D
Quick Check:
One camera at root covers all nodes [OK]
Hint: Leaves uncovered -> camera at parent -> minimal cameras [OK]
Common Mistakes:
Counting cameras on leaves instead of parent
Forgetting to add camera at root if uncovered
Misinterpreting coverage states
2. Given a binary tree and a target sum, you need to count all paths where the sum of the node values along the path equals the target. The path can start and end at any node but must go downwards (parent to child). Which approach guarantees an optimal solution in terms of time complexity?
easy
A. Use a brute force DFS starting from every node, checking all downward paths for the target sum.
B. Use dynamic programming to store sums of subtrees and combine results bottom-up.
C. Use a DFS with a prefix sum hash map to track cumulative sums and count valid paths in one traversal.
D. Use a greedy approach to prune paths that exceed the target sum early.
Solution
Step 1: Understand problem constraints and path definition
The path can start and end anywhere but must go downwards, so checking all paths naively is expensive.
Step 2: Recognize prefix sum with DFS pattern
Using a prefix sum hash map during DFS allows counting all valid paths in O(n) time by tracking cumulative sums and their frequencies.
Using brute force DFS from every node without pruning
Trying greedy pruning which fails on negative values
3. The following code attempts to check if a binary tree is balanced using iterative postorder traversal. Which line contains a subtle bug that can cause incorrect results on an empty tree or null root?
medium
A. Line 1: Missing check for empty root before traversal
B. Line 7: Incorrectly pushing node.left without null check
C. Line 12: Comparing last_visited with peek.right incorrectly
D. Line 16: Using abs difference without considering null children
Solution
Step 1: Identify handling of empty tree
The code does not check if root is None before starting traversal, which can cause errors or incorrect results.
Step 2: Verify other lines
Other lines handle null children safely using heights.get with default 0, and last_visited logic is correct.
Final Answer:
Option A -> Option A
Quick Check:
Missing early return for empty root causes bug [OK]
Hint: Always check for empty root before traversal [OK]
4. Suppose the problem is modified so that cameras can monitor nodes up to distance 2 away (i.e., parent, self, children, and grandchildren). Which change to the algorithm is necessary to maintain minimal camera placement?
hard
A. Use the same three-state postorder traversal but add a fourth state to track grandchildren coverage
B. Place cameras greedily on all nodes with uncovered children as before, no change needed
C. Modify DFS to track coverage states up to distance 2 and place cameras accordingly, increasing state complexity
D. Switch to brute force recursion since greedy no longer works
Solution
Step 1: Understand coverage radius increase
Cameras now cover nodes up to distance 2, so coverage states must reflect grandchildren coverage, not just immediate children.
Step 2: Adjust algorithm states
The original three states are insufficient; DFS must track coverage at a larger radius, increasing complexity and requiring more nuanced state management.
Step 3: Evaluate options
Simply adding a fourth state (A) is vague and insufficient without redesign. Greedy placement without state changes (B) fails minimality. Brute force (D) is inefficient and unnecessary.
Final Answer:
Option C -> Option C
Quick Check:
Expanded coverage radius requires more complex state tracking [OK]
Hint: Larger coverage radius -> more complex states in DFS [OK]
Common Mistakes:
Assuming original states suffice for extended coverage
Relying on naive greedy placement
Switching to brute force unnecessarily
5. Suppose the problem is extended: the tree nodes can have duplicate values, and you want to check if the tree is symmetric ignoring node values, only structure matters. Which modification to the original DFS approach correctly solves this variant?
hard
A. Keep the value comparison but add a hash map to track visited nodes to avoid duplicates.
B. Use BFS level-order traversal and check if each level forms a palindrome of node values.
C. Modify the base case to return true if both nodes are null, and skip the value comparison step entirely.
D. Perform a preorder traversal and compare the traversal list with its reverse.
Solution
Step 1: Understand the variant ignores node values, only structure matters
Therefore, the value comparison step must be removed to avoid false negatives due to duplicates.
Step 2: Modify the DFS to only check if both nodes exist or are null, recursively comparing mirrored subtrees
Return true if both nodes are null; otherwise, recurse on mirrored children without comparing values.
Final Answer:
Option C -> Option C
Quick Check:
Ignoring values means skipping value checks but preserving mirrored structure checks [OK]
Hint: Ignore values, check only mirrored structure recursively [OK]
Common Mistakes:
Keeping value checks causing false negatives
Using BFS palindrome checks which fail on structure
Using preorder traversal which ignores mirrored structure
Recommended
Ready to prove it?
Pass the test and this pattern moves unknownstrongwhile earning +1 Grip toward your certificate.