Maximum Width of Binary Tree in DSA Python

Mental Model

We want to find the widest level in a tree by counting nodes including gaps between them.

Analogy: Imagine a family tree photo where some people stand far apart; the width counts all spaces between the leftmost and rightmost person.

       1
      / \
     3   2
    /     \
   5       9
  /         \
 6           7

Dry Run Walkthrough

Input: Binary tree: 1 -> 3,2 -> 5,null,null,9 -> 6,null,null,null,null,null,7

Goal: Find the maximum width among all levels, counting null gaps between nodes.

Step 1: Start at root with index 0 in queue

[(1,0)]

Why: We assign index 0 to root to track positions for width calculation

Step 2: Process level 1: nodes [(1,0)]

Level width = 0 - 0 + 1 = 1

Why: Only root node, width is 1

Step 3: Add children with indices: left child (3,1), right child (2,2)

[(3,1), (2,2)]

Why: Left child index = 2*0+1=1, right child index = 2*0+2=2

Step 4: Process level 2: nodes [(3,1), (2,2)]

Level width = 2 - 1 + 1 = 2

Why: Width counts from leftmost to rightmost indices

Step 5: Add children: (5,3) from 3, (9,6) from 2; null children skipped

[(5,3), (9,6)]

Why: Indices: left child = 2*1+1=3, right child = 2*2+2=6

Step 6: Process level 3: nodes [(5,3), (9,6)]

Level width = 6 - 3 + 1 = 4

Why: Width includes gaps between indices 3 and 6

Step 7: Add children: (6,7) from 5, (7,14) from 9; null children skipped

[(6,7), (7,14)]

Why: Indices: left child = 2*3+1=7, right child = 2*6+2=14

Step 8: Process level 4: nodes [(6,7), (7,14)]

Level width = 14 - 7 + 1 = 8

Why: Maximum width found at this level

Result:

Maximum width = 8

Annotated Code

DSA Python

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: TreeNode) -> int:
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 0)])  # node with index
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]  # index of first node at this level
        for i in range(level_length):
            node, index = queue.popleft()
            # normalize index to prevent overflow
            index -= first_index
            if node.left:
                queue.append((node.left, 2 * index + 1))
            if node.right:
                queue.append((node.right, 2 * index + 2))
            if i == level_length - 1:
                max_width = max(max_width, index + 1)
    return max_width

# Driver code to build the example tree and test
root = TreeNode(1)
root.left = TreeNode(3)
root.right = TreeNode(2)
root.left.left = TreeNode(5)
root.right.right = TreeNode(9)
root.left.left.left = TreeNode(6)
root.right.right.right = TreeNode(7)

print(widthOfBinaryTree(root))

queue = deque([(root, 0)]) # node with index

start BFS with root node at index 0

_, first_index = queue[0] # index of first node at this level

record first node index to normalize indices at this level

index -= first_index

normalize index to avoid large numbers and keep relative positions

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

assign left child index based on current node index

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

assign right child index based on current node index

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

update max width using last node's normalized index + 1

Output

8

Complexity Analysis

Time: O(n) because we visit each node once in BFS

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Compared to naive level traversal without indices, this method efficiently tracks gaps and handles sparse trees

Edge Cases

Empty tree

Returns width 0 immediately

DSA Python

if not root:
    return 0

Single node tree

Width is 1 as only root exists

DSA Python

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

Tree with missing children causing gaps

Indices track gaps correctly to count width including nulls

DSA Python

index -= first_index

When to Use This Pattern

When asked for the widest level in a tree including gaps, use BFS with index tracking to measure width accurately.

Common Mistakes

Mistake: Not normalizing indices each level causing integer overflow or wrong width
Fix: Subtract first node's index at each level from all indices to keep them small and relative

Mistake: Counting only existing nodes ignoring gaps between them
Fix: Use indices to include null gaps between leftmost and rightmost nodes

Summary

Finds the maximum width of a binary tree counting null gaps between nodes.

Use when you need the widest level width including spaces in a sparse tree.

Track node positions with indices during BFS and normalize per level to measure width.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The total number of nodes in the tree

B. The height of the tree

C. The maximum number of nodes present at any level of the tree

D. The sum of values of nodes at the widest level

Solution

1. Step 1: Understand the term "width" in binary trees

   The width of a binary tree at a level is the count of nodes present at that level.

2. Step 2: Define maximum width

   The maximum width is the largest such count among all levels of the tree.

3. Final Answer:

   The maximum number of nodes present at any level of the tree -> Option C

4. Quick Check:

   Width means node count per level = maximum width [OK]

Hint: Maximum width = max nodes in any single level [OK]

Common Mistakes:

• Confusing width with height
• Counting total nodes instead of per level
• Summing node values instead of counting nodes

2. Which of the following Python code snippets correctly initializes a queue to help find the maximum width of a binary tree?

easy

A. queue = [(root, 0)]

B. queue = [root]

C. queue = root

D. queue = []

Solution

1. Step 1: Understand queue usage in width calculation

   We use a queue to hold nodes along with their position indices to track width.

2. Step 2: Check correct initialization

   Initializing queue as a list of tuples with (node, index) is correct: [(root, 0)].

3. Final Answer:

   queue = [(root, 0)] -> Option A

4. Quick Check:

   Queue holds (node, index) pairs = correct initialization [OK]

Hint: Use (node, index) pairs in queue for width tracking [OK]

Common Mistakes:

• Using queue = [root] without index
• Assigning queue = root (not a list)
• Starting with empty queue []

3. What is the output of the following code snippet that calculates the maximum width of a binary tree?

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = [(root, 0)]
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for i in range(level_length):
            node, index = queue.pop(0)
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))
        max_width = max(max_width, index - first_index + 1)
    return max_width

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.right = Node(5)
print(widthOfBinaryTree(root))

medium

A. 3

B. 2

C. 5

D. 4

Solution

1. Step 1: Trace the tree structure and indices

   Level 0: Node 1 at index 0 (width 1) Level 1: Nodes 2 (index 0), 3 (index 1) width = 2 Level 2: Nodes 4 (index 0), 5 (index 3) width = 3 - 0 + 1 = 4

2. Step 2: Calculate max width

   Maximum width is 4 at level 2.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Max width = 4 nodes wide at level 2 [OK]

Hint: Track indices to find width = last - first + 1 [OK]

Common Mistakes:

• Ignoring index gaps causing wrong width
• Using length of queue directly as width
• Not updating max_width correctly

4. Identify the bug in this code snippet that attempts to find the maximum width of a binary tree:

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = [(root, 0)]
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for i in range(level_length):
            node, index = queue.pop(0)
            if node.left:
                queue.append((node.left, index * 2 + 1))
            if node.right:
                queue.append((node.right, index * 2 + 2))
        max_width = max(max_width, index - first_index + 1)
    return max_width

medium

A. Left and right child indices are swapped; should be 2*index and 2*index+1

B. Queue should be a stack for correct traversal

C. max_width update is outside the while loop

D. Missing check for empty tree at start

Solution

1. Step 1: Check child index calculation

   Correct indices for left and right children are 2*index and 2*index+1 respectively.

2. Step 2: Identify incorrect index formula

   Code uses index*2+1 for left and index*2+2 for right, which is swapped and incorrect.

3. Final Answer:

   Left and right child indices are swapped; should be 2*index and 2*index+1 -> Option A

4. Quick Check:

   Child indices must be 2*i and 2*i+1 [OK]

Hint: Left child = 2*i, right child = 2*i+1 [OK]

Common Mistakes:

• Swapping left and right child indices
• Using stack instead of queue
• Updating max_width outside loop

5. Given a binary tree where some levels have missing nodes, which approach correctly calculates the maximum width including gaps between nodes?
Choose the best method to handle this scenario.

hard

A. Count only existing nodes at each level ignoring gaps

B. Use level order traversal with node indices to calculate width as last_index - first_index + 1

C. Calculate width as the maximum depth of the tree

D. Sum the values of nodes at each level and find the maximum sum

Solution

1. Step 1: Understand gaps in tree levels

   Missing nodes create gaps, so counting nodes alone misses width.

2. Step 2: Use indices to include gaps

   Assign indices to nodes as if tree was complete; width = last_index - first_index + 1.

3. Step 3: Apply level order traversal with indices

   This method captures true width including empty spaces between nodes.

4. Final Answer:

   Use level order traversal with node indices to calculate width as last_index - first_index + 1 -> Option B

5. Quick Check:

   Index-based width includes gaps = correct max width [OK]

Hint: Use indices to count gaps for true width [OK]

Common Mistakes:

• Ignoring gaps by counting nodes only
• Using tree depth as width
• Summing node values instead of counting width