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. Given the following Morris preorder traversal code, what is the final output list after running preorderTraversal on the tree below? Tree structure:

    1
   / \
  2   3

def preorderTraversal(root):
    result = []
    current = root
    while current:
        if current.left is None:
            result.append(current.val)
            current = current.right
        else:
            predecessor = current.left
            while predecessor.right and predecessor.right != current:
                predecessor = predecessor.right
            if predecessor.right is None:
                predecessor.right = current
                result.append(current.val)
                current = current.left
            else:
                predecessor.right = None
                current = current.right
    return result

easy

A. [2, 1, 3]

B. [1, 2, 3]

C. [1, 3, 2]

D. [3, 1, 2]

Solution

1. Step 1: Trace first iteration with current=1

   Node 1 has left child 2, predecessor is 2 with no right child, set 2.right=1, append 1, move current=2.

2. Step 2: Trace second iteration with current=2

   Node 2 has no left child, append 2, move current=2.right which points back to 1 (thread).

3. Step 3: Detect thread at 2.right=1

   Since predecessor.right == current, reset 2.right=None, move current=1.right=3.

4. Step 4: Trace current=3

   Node 3 has no left child, append 3, move current=3.right=None, loop ends.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Output matches preorder traversal [1,2,3] [OK]

Hint: Morris preorder appends root before left subtree [OK]

Common Mistakes:

• Appending nodes in wrong order
• Not resetting threaded links
• Confusing left and right child traversal

2. Consider the following Python code implementing the Morris Preorder Traversal approach to sum root-to-leaf numbers. Given the binary tree: 1 / \ 2 3 What is the final value of the variable total returned by sumNumbers?

easy

A. 5

B. 15

C. 25

D. 26

Solution

1. Step 1: Trace path 1->2

   current_number accumulates 1 then 12; leaf node 2 adds 12 to total.

2. Step 2: Trace path 1->3

   current_number resets to 1, then accumulates 13; leaf node 3 adds 13 to total. Total = 12 + 13 = 25.

3. Step 3: Check for off-by-one or missed increments

   Integer division after visiting left subtree correctly adjusts current_number; no extra addition occurs.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Sum of 12 and 13 is 25, matching code behavior [OK]

Hint: Trace current_number updates carefully at each node [OK]

Common Mistakes:

• Off-by-one in current_number division
• Adding non-leaf nodes to total

3. Consider the following buggy code snippet for building a binary tree from preorder and inorder traversals. Which line contains the subtle bug that can cause incorrect tree construction or infinite loops?

medium

A. Line where stack is initialized with root

B. Line inside if block missing stack.append(node.left)

C. Line where root is initialized with preorder[0]

D. Line inside else block where inorder_index is incremented

Solution

1. Step 1: Identify missing operation

   Inside the if block, after creating node.left, the new node is not pushed onto the stack.

2. Step 2: Consequences of missing stack append

   Without pushing, the algorithm loses track of the left subtree root, causing incorrect tree or infinite loops.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Stack must track all nodes to correctly build tree [OK]

Hint: Always push newly created nodes to stack to track subtree roots [OK]

Common Mistakes:

• Forgetting to push left child nodes
• Incorrectly incrementing inorder_index
• Misinitializing root or stack

4. The following code attempts to solve the House Robber III problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 5: rob_current calculation uses left[0] and right[0]

B. Line 7: Returning (rob_current, not_rob_current)

C. Line 6: not_rob_current uses max(left) + max(right)

D. Line 2: Base case returns (0, 0)

Solution

1. Step 1: Understand rob_current calculation

   rob_current should be node.val plus the not_rob values of left and right children, because robbing current node forbids robbing immediate children.

2. Step 2: Identify the bug

   Line 5 incorrectly adds left[0] and right[0] (rob values of children), violating adjacency constraint.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using rob values of children overcounts and breaks correctness [OK]

Hint: Rob current node + not_rob children, not rob children [OK]

Common Mistakes:

• Mixing rob and not_rob indices in tuple
• Forgetting adjacency constraints

5. Suppose you want to invert a binary tree where nodes can have an arbitrary number of children (not just two). Which modification to the inversion algorithm correctly generalizes the inversion to this n-ary tree?

hard

A. Swap only the first and last child pointers recursively, leaving others unchanged.

B. Use BFS to swap children pairwise at each level without recursion.

C. Recursively invert each child's subtree, then reverse the list of children in-place.

D. Invert only the leftmost and rightmost subtrees recursively, ignoring middle children.

Solution

1. Step 1: Understand inversion for binary tree swaps left and right children

   For n-ary trees, inversion means reversing the order of children after inverting each child's subtree.

2. Step 2: Generalize recursion and reversal

   Recursively invert each child's subtree, then reverse the children list to mirror the tree structure.

3. Step 3: Evaluate other options

   Swapping only first and last or partial BFS swaps do not fully invert the tree structure.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Recursion plus reversing children list generalizes inversion correctly [OK]

Hint: Invert subtrees recursively, then reverse children list for n-ary trees [OK]

Common Mistakes:

• Swapping only some children pairs
• Ignoring recursion on all children
• Using BFS without recursion for full inversion