Maximum Width of Binary Tree: Index-Based BFS

Given the root of a binary tree, return the maximum width of the tree. The width of a level is defined as the length between the leftmost and rightmost non-null nodes, where null nodes between the endpoints count toward the length. This is LeetCode 662: Maximum Width of Binary Tree.

For example, given root = [1, 3, 2, 5, 3, null, 9], the output is 4. Level 2 has nodes 5, 3, null, and 9. Even though one slot is empty, the width stretches from the leftmost node (5) to the rightmost node (9), giving a width of 4.

Approach

The trick is to avoid actually storing null nodes. Instead, you assign each node a position index using the same numbering scheme as a binary heap. The root gets position 1. For any node at position i, its left child sits at 2 * i and its right child sits at 2 * i + 1.

With this indexing, the width of any level is simply rightmost_position - leftmost_position + 1. Null gaps are accounted for automatically because the position numbers skip over them.

Run BFS level by level. At each level, record the position of the first node (leftmost) and the last node (rightmost). Compute the width as the difference plus one. Track the maximum width seen across all levels.

One subtlety: on very deep trees, the position values can grow exponentially. To keep numbers small, you can normalize positions at each level by subtracting the leftmost position. This prevents integer overflow in languages with fixed-width integers. In Python, integers have arbitrary precision, so overflow is not a concern, but normalizing is still a good habit.

The Python solution

from collections import deque

def width_of_binary_tree(root):
    if not root:
        return 0
    max_width = 0
    queue = deque([(root, 1)])
    while queue:
        level_size = len(queue)
        left_pos = queue[0][1]
        right_pos = left_pos
        for _ in range(level_size):
            node, pos = queue.popleft()
            right_pos = pos
            if node.left:
                queue.append((node.left, 2 * pos))
            if node.right:
                queue.append((node.right, 2 * pos + 1))
        max_width = max(max_width, right_pos - left_pos + 1)
    return max_width

Here is what each part does:

• queue = deque([(root, 1)]) seeds BFS with the root node and its position index of 1.
• left_pos = queue[0][1] captures the position of the first node in the current level. Since BFS processes nodes left to right, the first node in the queue is always the leftmost.
• right_pos = pos updates on every dequeue, so after the inner loop finishes it holds the rightmost position at that level.
• 2 * pos and 2 * pos + 1 assign positions to children using the binary heap indexing formula.
• right_pos - left_pos + 1 computes the width of the current level, including any null gaps in between.

Visual walkthrough

Trace BFS through the tree [1, 3, 2, 5, 3, null, 9]. Watch how each node receives a position index, and how the width at each level is computed from the leftmost and rightmost positions.

At level 0, the root is alone with position 1, so the width is 1. At level 1, nodes 3 and 2 sit at positions 2 and 3, giving a width of 2. At level 2, nodes 5, 3, and 9 sit at positions 4, 5, and 7. Even though position 6 is null, the width spans from 4 to 7, giving 4. The maximum across all levels is 4.

Complexity analysis

The time is linear because BFS visits each node once. The space is O(n) in the worst case because the bottom level of a complete binary tree holds roughly half of all nodes. For a skewed tree, the queue holds at most one node per level, but the worst case is still O(n).

Building blocks

This problem is built on two reusable patterns:

1. BFS level-by-level processing. The template snapshots the queue size at the start of each level and drains exactly that many nodes:

from collections import deque

def bfs_by_level(root):
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            node = queue.popleft()
            for child in [node.left, node.right]:
                if child:
                    queue.append(child)

2. Binary heap position indexing. Assign position 1 to the root, 2 * i to the left child, and 2 * i + 1 to the right child. This lets you compute distances between nodes at the same level without materializing null placeholders. The same indexing appears in problems like "Complete Binary Tree Inserter" and serialization tasks.

These two building blocks combine naturally. BFS gives you level boundaries. Position indexing gives you the span of each level. Together, computing the maximum width requires no extra data structures beyond the queue.

Edge cases

• Empty tree (root is None): return 0. The guard clause at the top handles this.
• Single node (no children): return 1. The root is at position 1, and the width of a single node is 1 - 1 + 1 = 1.
• Complete binary tree: every level is full, so the width at level d is 2^d. The maximum width is the bottom level.
• Skewed tree (every node has only one child): each level has one node, so the width at every level is 1. The maximum width is 1.

From understanding to recall

You just traced through a BFS solution that uses binary heap indexing to compute level widths without tracking nulls. The formula rightmost - leftmost + 1 makes sense right now. But in a timed interview, will you remember to assign position 1 to the root and use 2 * i and 2 * i + 1 for children? Will you recall that you need to subtract the leftmost position to get the width?

Understanding a pattern and reproducing it under pressure are different skills. Spaced repetition bridges that gap. You practice writing the BFS template with position tracking from memory at increasing intervals. First after a day, then three days, then a week. Each repetition reinforces the indexing formula and the width calculation until the pattern becomes automatic.

Position-indexed BFS is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Drilling them individually with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Binary Tree Right Side View - Another BFS level-by-level problem where you extract specific information from each level
• Binary Tree Level Order Traversal - The base BFS level-by-level template that this problem builds on
• Binary Tree Zigzag Level Order Traversal - A BFS variation that alternates direction at each level, using the same level-size snapshot technique