Maximum Width of Binary Tree

▶

Steps

setup

Initialize queue with root node and index 0

Start by placing the root node (value 1) in the queue with index 0, representing its position in a full binary tree.

💡 This sets the foundation for BFS traversal and indexing to measure width.

Line:

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

💡 Index 0 represents the root's position; all other nodes will be indexed relative to this.

fill_row

Start processing level 0

Note the length of the queue (1) and record the first index (0) as offset for normalization.

💡 Offset helps normalize indices to prevent integer overflow and measure width relative to level start.

Line:

level_length = len(queue)
_, first_index = queue[0]

💡 Normalizing indices by subtracting offset aligns the level's indices starting at 0.

fill_cells

Process node 1 at level 0

Dequeue node 1 with index 0, normalize index by subtracting offset 0 (index remains 0).

💡 Normalization keeps indices manageable and relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 1 is at normalized index 0 at level 0.

fill_cells

Enqueue children of node 1

Add left child (3) with index 0*2=0 and right child (2) with index 0*2+1=1 to the queue.

💡 Children indices reflect their position in a full binary tree, preserving gaps.

Line:

if node.left:
    queue.append((node.left, 2 * index))
if node.right:
    queue.append((node.right, 2 * index + 1))

💡 Indices 0 and 1 for children show they are adjacent at next level.

compare

Update max width after level 0

Calculate width as last normalized index + 1 = 0 + 1 = 1, update max_width to 1.

💡 Width at level 0 is 1 because only root node exists.

Line:

if i == level_length - 1:
    max_width = max(max_width, index + 1)

💡 Max width starts at 1 after processing root level.

fill_row

Start processing level 1

Level length is 2; first index in queue is 0, set offset to 0 for normalization.

💡 Offset resets per level to keep indices small and relative.

Line:

level_length = len(queue)
_, first_index = queue[0]

💡 Normalization will align indices at this level starting from 0.

fill_cells

Process node 3 (left child of root) at level 1

Dequeue node 3 with index 0, normalize index by subtracting offset 0 (index remains 0).

💡 Normalization keeps indices relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 3 is at normalized index 0 at level 1.

fill_cells

Enqueue children of node 3

Add left child (5) with index 2*0=0 and right child (3) with index 2*0+1=1 to the queue.

💡 Children indices reflect their position in the full binary tree at this level.

Line:

if node.left:
    queue.append((node.left, 2 * index))
if node.right:
    queue.append((node.right, 2 * index + 1))

💡 Indices 0 and 1 for children show their relative positions at next level.

fill_cells

Process node 2 (right child of root) at level 1

Dequeue node 2 with index 1, normalize index by subtracting offset 0 (index remains 1).

💡 Normalization aligns indices relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 2 is at normalized index 1 at level 1.

fill_cells

Enqueue right child of node 2

Node 2 has no left child, but right child (9) is added with index 2*1+1=3.

💡 Index 3 reflects the child's position in the full binary tree, leaving a gap at index 2.

Line:

if node.right:
    queue.append((node.right, 2 * index + 1))

💡 Index 3 shows a gap at index 2, important for width calculation.

compare

Update max width after level 1

Width is last normalized index + 1 = 1 + 1 = 2, max_width updated from 1 to 2.

💡 Width at level 1 is 2 because nodes are at indices 0 and 1.

Line:

if i == level_length - 1:
    max_width = max(max_width, index + 1)

💡 Max width updated to 2 after processing second level.

fill_row

Start processing level 2

Level length is 3; first index in queue is 0, set offset to 0 for normalization.

💡 Offset resets to normalize indices at this level.

Line:

level_length = len(queue)
_, first_index = queue[0]

💡 Normalization aligns indices starting at 0 for this level.

fill_cells

Process node 5 at level 2

Dequeue node 5 with index 0, normalize index by subtracting offset 0 (index remains 0).

💡 Normalization aligns indices relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 5 is at normalized index 0 at level 2.

fill_cells

Process node 3 (right child of node 3) at level 2

Dequeue node 3 with index 1, normalize index by subtracting offset 0 (index remains 1).

💡 Normalization keeps indices relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 3 is at normalized index 1 at level 2.

fill_cells

Process node 9 (right child of node 2) at level 2

Dequeue node 9 with index 3, normalize index by subtracting offset 0 (index remains 3).

💡 Normalization aligns indices relative to level start.

Line:

node, index = queue.popleft()
index -= first_index

💡 Node 9 is at normalized index 3 at level 2, showing a gap at index 2.

compare

Update max width after level 2

Width is last normalized index + 1 = 3 + 1 = 4, update max_width from 2 to 4.

💡 Width includes null gap at index 2, showing maximum width of the tree.

Line:

if i == level_length - 1:
    max_width = max(max_width, index + 1)

💡 Max width is 4, reflecting the widest level including null positions.

reconstruct

Traversal complete, return max width

Queue is empty, traversal ends. Return max_width = 4 as the maximum width of the binary tree.

💡 The algorithm has processed all levels and found the maximum width including gaps.

Line:

return max_width

💡 Maximum width is 4, matching the expected output.

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 widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])  # STEP 1: Initialize queue with root and index 0
    while queue:
        level_length = len(queue)  # STEP 2: Get current level length
        _, first_index = queue[0]  # STEP 2: Record first index as offset
        for i in range(level_length):
            node, index = queue.popleft()  # STEP 3: Dequeue node and index
            index -= first_index  # STEP 3: Normalize index
            if node.left:
                queue.append((node.left, 2 * index))  # STEP 4: Enqueue left child
            if node.right:
                queue.append((node.right, 2 * index + 1))  # STEP 4: Enqueue right child
            if i == level_length - 1:
                max_width = max(max_width, index + 1)  # STEP 5: Update max width
    return max_width  # STEP 17: Return final max width

if __name__ == '__main__':
    root = TreeNode(1)
    root.left = TreeNode(3)
    root.right = TreeNode(2)
    root.left.left = TreeNode(5)
    root.left.right = TreeNode(3)
    root.right.right = TreeNode(9)
    print(widthOfBinaryTree(root))  # Output: 4

📊

Maximum Width of Binary Tree - Watch the Algorithm Execute, Step by Step

Watching this step-by-step BFS with indexing reveals how the algorithm accounts for gaps in the tree structure, which is not obvious from code alone.

Current node: 1

132539

BFS Queue

N1 (L0)

Current node: 1

132539

BFS Queue

N1 (L0)

Current node: 1

132539

132539

BFS Queue

N2 (L1)N3 (L1)

132539

BFS Queue

N2 (L1)N3 (L1)

Current node: 2

132539

BFS Queue

N2 (L1)N3 (L1)

Current node: 2

132539

BFS Queue

N3 (L1)

Current node: 2

132539

BFS Queue

N3 (L1)N4 (L2)N5 (L2)

Current node: 3

132539

BFS Queue

N4 (L2)N5 (L2)

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

Current node: 4

132539

BFS Queue

N4 (L2)N5 (L2)N6 (L2)

Current node: 4

132539

BFS Queue

N5 (L2)N6 (L2)

Current node: 5

132539

BFS Queue

N6 (L2)

Current node: 6

132539

132539

132539

Return: 4

Key Takeaways

✓ Index normalization at each level prevents integer overflow and aligns node positions relative to the level start.

This is hard to see from code alone because the subtraction of offset is subtle but critical for correctness.

✓ The maximum width includes null nodes between existing nodes, represented by gaps in indices.

Visualizing the indices shows how the algorithm counts these gaps, which is not obvious from reading code.

✓ The BFS queue maintains nodes paired with their conceptual full binary tree indices, enabling width calculation level by level.

Seeing the queue contents and index updates step-by-step clarifies how children are positioned and why indices are doubled.

Practice

1. 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

2. You are given a binary tree and need to find the shortest distance from the root node down to the nearest leaf node. Which algorithmic approach guarantees the optimal solution with minimal time complexity?

easy

A. Breadth-First Search (BFS) stopping at the first encountered leaf node

B. Dynamic Programming storing minimum depths for subtrees and combining results

C. Depth-First Search (DFS) exploring all paths to leaves and returning the minimum depth

D. Greedy approach choosing the child with the smaller value at each step

Solution

1. Step 1: Understand the problem requirement

   The problem asks for the minimum depth to a leaf node, which means the shortest path from root to any leaf.

2. Step 2: Identify the algorithm that finds shortest path in unweighted trees

   BFS explores nodes level by level and stops immediately when it finds the first leaf, ensuring the shortest path is found efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS stops at first leaf -> minimal depth found [OK]

Hint: Shortest path in trees -> BFS with early stop [OK]

Common Mistakes:

• Assuming DFS always finds minimum depth efficiently
• Confusing greedy value-based choice with shortest path
• Thinking DP is needed for simple tree traversal

3. The following code attempts to compute the average of levels in a binary tree. Identify the line containing the subtle bug that causes incorrect averages when the tree is empty or null.

medium

A. Line 2: Missing check for empty tree before initializing queue

B. Line 5: Incorrect initialization of level_sum to zero

C. Line 9: Using popleft() instead of pop() on queue

D. Line 13: Appending average without converting to float

Solution

1. Step 1: Check for empty tree handling

   Code initializes queue with root without checking if root is None, causing queue to contain None.

2. Step 2: Consequence of missing check

   When root is None, popleft() returns None, and accessing node.val causes an error.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Adding "if not root: return []" fixes the bug [OK]

Hint: Always check for empty input before queue initialization [OK]

Common Mistakes:

• Forgetting empty tree check
• Misusing queue methods
• Integer division truncation (not here)

4. The following code attempts to determine if two nodes are cousins in a binary tree using BFS. Identify the line containing the subtle bug that causes incorrect results in some cases.

def isCousins(root, x, y):
    if not root:
        return False
    queue = deque([root])
    while queue:
        size = len(queue)
        x_parent = y_parent = None
        for _ in range(size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
                if node.left.val == x:
                    x_parent = node
                if node.left.val == y:
                    y_parent = node
            if node.right:
                queue.append(node.right)
                if node.right.val == x:
                    x_parent = node
                if node.right.val == y:
                    y_parent = node
        if x_parent or y_parent:
            return x_parent != y_parent
    return False

medium

A. Line resetting x_parent and y_parent to None at each level

B. Line returning x_parent != y_parent when only one parent is found

C. Line appending children to the queue

D. Line checking if root is null at the start

Solution

1. Step 1: Understand the bug

   The condition 'if x_parent or y_parent:' returns immediately even if only one node is found, which is incorrect.

2. Step 2: Correct logic

   Should return only if both parents are found; otherwise, continue searching or return false after level ends.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Returning on partial discovery causes false positives [OK]

Hint: Return only when both parents found, not one [OK]

Common Mistakes:

• Confusing siblings as cousins
• Not resetting parent pointers each level
• Returning too early when only one node found

5. The following code attempts to find the minimum depth of a binary tree using recursion. Identify the bug that causes incorrect results when one child is missing.

def minDepth(root):
    if not root:
        return 0
    if not root.left and not root.right:
        return 1
    left_depth = minDepth(root.left)
    right_depth = minDepth(root.right)
    return min(left_depth, right_depth) + 1

medium

A. Line 3: base case for leaf nodes is incorrect

B. Line 5: missing check for null root

C. Line 6: min() used without checking if one child is null

D. Line 7: missing +1 to account for current node

Solution

1. Step 1: Understand the bug with missing children

   If one child is null, minDepth returns 0 for that side, causing min() to pick 0 incorrectly.

2. Step 2: Why this causes wrong minimum depth

   Using min() blindly returns 1 instead of the correct depth from the non-null child, underestimating depth.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Bug is in min() usage without null child check -> incorrect depth [OK]

Hint: min() on zero from null child causes wrong depth [OK]

Common Mistakes:

• Assuming min() works without null checks
• Confusing min and max for depth calculation
• Ignoring base cases for leaf nodes