Maximum Depth of Binary Tree

▶

Steps

setup

Check if root is null

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.

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. You need to output all nodes of a binary tree such that each node is processed only after its left and right children have been processed. Which traversal approach guarantees this order?

easy

A. Postorder traversal using depth-first search

B. Preorder traversal using recursion

C. Level-order traversal using a queue

D. Inorder traversal using recursion

Solution

1. Step 1: Understand traversal order requirements

   Postorder traversal processes left subtree, then right subtree, then the node itself, ensuring children are processed before the parent.

2. Step 2: Compare with other traversals

   Preorder and inorder do not guarantee children processed before parent; level-order processes nodes by depth, not child-first.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Postorder traversal matches the problem's processing order [OK]

Hint: Postorder processes children before parent [OK]

Common Mistakes:

• Confusing inorder with postorder
• Thinking preorder processes children first

2. The following code attempts to count nodes in a complete binary tree using the optimal approach. Identify the line containing the subtle bug that can cause incorrect counts for incomplete last levels.

def exists(idx, h, root):
    left, right = 0, 2**(h - 1) - 1
    for _ in range(h - 1):
        mid = (left + right) // 2
        if idx < mid:  # Bug here
            root = root.left
            right = mid
        else:
            root = root.right
            left = mid + 1
    return root is not null

medium

A. Line with 'if idx < mid:'

B. Line with 'return root is not null'

C. Line with 'root = root.right'

D. Line with 'left, right = 0, 2**(h - 1) - 1'

Solution

1. Step 1: Understand binary search condition

   The condition should be 'if idx <= mid' to correctly include mid index in left subtree.

2. Step 2: Identify impact of bug

   Using 'idx < mid' excludes mid index from left subtree, causing incorrect traversal and wrong node existence checks.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct binary search must include mid index [OK]

Hint: Binary search must use <= to include mid index [OK]

Common Mistakes:

• Using < instead of <= in binary search condition

3. Examine the following buggy code snippet for summing root-to-leaf numbers using DFS recursion. Which line contains the subtle bug causing incorrect sums on some inputs?

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        self.total = 0
        def dfs(node, current_number):
            if not node:
                return
            current_number = current_number * 10 + node.val
            self.total += current_number  # Bug here
            if not node.left and not node.right:
                return
            dfs(node.left, current_number)
            dfs(node.right, current_number)
        dfs(root, 0)
        return self.total

medium

A. Line with 'if not node:' return statement

B. Line adding current_number to self.total

C. Line checking if node is leaf

D. Line calling dfs on node.right

Solution

1. Step 1: Understand when sums should be added

   Sum should only include complete root-to-leaf numbers, so addition must happen only at leaf nodes.

2. Step 2: Identify incorrect addition

   Adding current_number at every node (including non-leaf) causes partial numbers to be summed, inflating total incorrectly.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sum only at leaves fixes the bug [OK]

Hint: Add to total only at leaf nodes [OK]

Common Mistakes:

• Adding partial path sums at non-leaf nodes
• Not resetting total between calls

4. Suppose the problem changes: the binary tree is no longer complete but only a general binary tree. Which of the following statements about counting nodes efficiently is true?

hard

A. Breadth-first search (BFS) can count nodes in O(log n) time for any binary tree.

B. The optimal binary search approach on the last level still applies with minor modifications.

C. Using tree height to check perfect subtrees can still reduce time complexity to O((log n)^2).

D. A simple DFS traversal counting all nodes is the only guaranteed correct method with O(n) time.

Solution

1. Step 1: Understand the problem change

   The tree is no longer complete, so properties used by optimal methods do not hold.

2. Step 2: Identify correct counting method

   Only a full traversal (DFS or BFS) guarantees counting all nodes correctly in O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal methods rely on completeness, which is lost here [OK]

Hint: Without completeness, must traverse all nodes [OK]

Common Mistakes:

• Trying to apply binary search on last level
• Assuming height checks still reduce complexity

5. Suppose you want to extend the serialization/deserialization to support binary trees where nodes can have duplicate values and the tree can be very deep (height > 10,000). Which modification is necessary to ensure correctness and efficiency?

hard

A. Use iterative BFS serialization with null markers and iterative deserialization to avoid recursion stack overflow.

B. Use recursive DFS with memoization to handle duplicates and deep trees efficiently.

C. Switch to preorder traversal without null markers to reduce string size and recursion depth.

D. Serialize only unique node values and reconstruct tree assuming balanced shape.

Solution

1. Step 1: Identify problem with deep recursion

   Recursive DFS can cause stack overflow on very deep trees.

2. Step 2: Use iterative BFS with null markers

   Iterative BFS avoids recursion stack issues and null markers preserve structure even with duplicates.

3. Step 3: Avoid assumptions about uniqueness or balanced shape

   Duplicates require storing all nodes explicitly; balanced assumptions break correctness.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Iterative BFS with null markers handles deep trees and duplicates safely [OK]

Hint: Iterative BFS avoids recursion limits and preserves structure [OK]

Common Mistakes:

• Removing null markers to save space breaks reconstruction
• Using recursion on deep trees causes stack overflow
• Assuming unique values or balanced trees