Maximum Width of Binary Tree — Solution

Problem

Given a binary tree, find the maximum width among all of its levels. The width of a level is the number of positions between the leftmost and rightmost nodes, counting every null slot in between as if it were filled. Only the outermost non-null nodes determine the endpoints — interior nulls count toward the width but a trailing null at the right end does not extend it.

[1,3,2,5,3,null,9]

• Input: root = [1, 3, 2, 5, 3, null, 9]
• Output: 4
• Explanation: The bottom level spans positions 0 through 3 — nodes 5, 3, a null gap, and 9 — giving a width of 4.

Intuition

Think of a complete binary tree where every node at index i has a left child at 2i and a right child at 2i + 1. Even in a sparse tree, we can label each node with the index it would hold in that imagined complete tree. The width of any level is simply rightmost_index - leftmost_index + 1. BFS lets us process one level at a time, so we just need to track how spread apart the leftmost and rightmost indices are on each pass.

The subtle issue is that these indices double with every level — a tree of depth 30 would produce indices larger than 2³⁰. The fix is to normalize: subtract the leftmost index from every node's position at the start of each level. The relative gaps are preserved, and the numbers stay small.

Solution — BFS with Position Indexing

Process the tree level by level with BFS. Carry each node's imagined complete-tree index through the queue. At the start of each level, normalize all indices by subtracting the first position so they never grow large. The width of the level is last_normalized_index + 1 (since the normalized leftmost is always 0).

1. Enqueue the root with position 0.
2. For each level, note the position of the very first node — this is the normalization offset.
3. Process each node: subtract the offset to get its normalized position, then enqueue its children at 2 * normalized_pos and 2 * normalized_pos + 1.
4. After finishing the level, the last normalized position seen equals width - 1.
5. Update the running maximum and repeat.

1from collections import deque
2
3def widthOfBinaryTree(root):
4    if not root:
5        return 0
6
7    max_width = 0
8    queue = deque([(root, 0)])  # (node, position in imagined complete tree)
9
10    while queue:
11        level_size = len(queue)
12        level_offset = queue[0][1]  # leftmost position — subtract this to normalize
13        last_normalized = 0
14
15        for _ in range(level_size):
16            node, pos = queue.popleft()
17            normalized_pos = pos - level_offset  # keep indices from overflowing
18            last_normalized = normalized_pos
19
20            if node.left:
21                queue.append((node.left, 2 * normalized_pos))
22            if node.right:
23                queue.append((node.right, 2 * normalized_pos + 1))
24
25        max_width = max(max_width, last_normalized + 1)  # +1 because both ends are inclusive
26
27    return max_width

Time: O(n) — every node is visited exactly once during BFS.

Space: O(n) — the queue holds at most all nodes on the widest level, which can be up to n/2 nodes in a complete binary tree.

Complexity Summary

Common Mistakes

• Using int for positions instead of long — indices double at each level, so a tree 32 levels deep would overflow a 32-bit integer even before normalization. Always use long (Java) or long long (C++).
• Skipping normalization — even with 64-bit integers, a tree of depth 64 would produce positions exceeding 2⁶³. Subtracting the leftmost position at the start of each level resets the range to zero-based and prevents overflow.
• Computing width as last - first instead of last - first + 1 — both the leftmost and rightmost nodes are included, so the span needs the extra 1. A single-node level has width 1, not 0.
• Filling the queue with null placeholders — a common brute-force idea is to insert null sentinels for every absent child so you can count total slots per level. This blows up to O(2^depth) queue size and will time out on deep unbalanced trees.
• Confusing null gaps with trailing nulls — a null between two non-null nodes counts toward the width, but nulls past the rightmost non-null node do not. The position-index approach handles this automatically since you only look at the first and last non-null node positions.

Related Problems

• binary-tree-level-order-traversal — foundational BFS-per-level pattern this solution builds on
• binary-tree-right-side-view — also picks a single representative node per level using BFS
• binary-tree-zigzag-level-order-traversal — level-by-level BFS with a direction toggle per depth
• maximum-depth-of-binary-tree — counts levels rather than measuring span, same BFS framing
• maximum-level-sum-of-a-binary-tree — aggregates values per level with the same BFS template