Maximum Width of Binary Tree — LC 662 BFS Indexing Trick

Problem Statement#

Given the root of a binary tree, return the maximum width. The width of one level is the number of nodes between the leftmost and rightmost non-null nodes at that level, where null nodes between the endpoints are also counted.

Constraints:

• The number of nodes is in the range [1, 3000]
• -100 <= Node.val <= 100

Input:  root = [1,3,2,5,3,null,9]
Output: 4
        Level 2 spans positions 0..3 (5,3,_,9)

Input:  root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
        Level 3 spans positions 0..6 (6,_,_,_,_,_,7)

Why This Problem Matters#

LeetCode 662 Maximum Width of Binary Tree is a Medium-difficulty interview question popular at Amazon, Meta, Microsoft, and Bloomberg. It tests three things at once: BFS level traversal, the heap-style index encoding (left = 2i, right = 2i + 1), and integer-overflow awareness on deep trees.

The problem separates candidates who only know "do BFS level by level" from those who can attach metadata to BFS state. It is also a gateway to understanding how heaps and segment trees physically lay nodes out in arrays — a pattern that recurs in priority queues and Fenwick trees.

Production engineers see the same pattern when implementing serialized binary tree storage formats or computing row spans in tree visualizations.

The Core Insight#

Imagine the tree embedded in a perfect binary tree where every position has an index. The root is index 0, its children are 0 and 1, grandchildren are 0, 1, 2, 3, and so on. A node at index i has children at 2i and 2i + 1. The width of any level is rightmost_index - leftmost_index + 1.

The naive implementation overflows: at depth 32, indices reach 2^32. The fix is per-level normalization: at the start of each BFS level, subtract the leftmost index from every node's index so the level starts at 0 again. This keeps numbers small while preserving widths because subtracting a constant from both endpoints leaves their difference unchanged.

Visual Dry Run#

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

Maximum width = 4.

Solution (Optimal)#

from collections import deque
 
class Solution:
    def widthOfBinaryTree(self, root) -> int:
        if not root:
            return 0
        max_width = 0
        queue = deque([(root, 0)])
        while queue:
            level_size = len(queue)
            _, level_start = queue[0]
            last_idx = 0
            for _ in range(level_size):
                node, idx = queue.popleft()
                idx -= level_start  # normalize to prevent overflow
                last_idx = idx
                if node.left:
                    queue.append((node.left, 2 * idx))
                if node.right:
                    queue.append((node.right, 2 * idx + 1))
            max_width = max(max_width, last_idx + 1)
        return max_width

var widthOfBinaryTree = function(root) {
    if (!root) return 0;
    let maxWidth = 0;
    let queue = [[root, 0n]];
    while (queue.length) {
        const levelSize = queue.length;
        const levelStart = queue[0][1];
        let lastIdx = 0n;
        const next = [];
        for (let i = 0; i < levelSize; i++) {
            const [node, raw] = queue[i];
            const idx = raw - levelStart;
            lastIdx = idx;
            if (node.left)  next.push([node.left,  2n * idx]);
            if (node.right) next.push([node.right, 2n * idx + 1n]);
        }
        const w = Number(lastIdx) + 1;
        if (w > maxWidth) maxWidth = w;
        queue = next;
    }
    return maxWidth;
};

Time: O(n) — each node enqueued and dequeued once. Space: O(w) — queue holds at most one full level (up to n/2 nodes).

Common Mistakes#

• Not normalizing indices — overflows on deep trees beyond depth 32.
• Using regular JS numbers instead of BigInt — silent precision loss past 2^53.
• Computing width as count of non-null nodes — this misses null gaps that count.
• Off-by-one: width is right - left + 1, not right - left.
• Reading leftmost AFTER the loop popped it — capture queue[0] before dequeuing.

Interview Tips#

• Draw the tree, label every position with its complete-tree index, then circle leftmost and rightmost per level.
• Mention overflow up front: "I'll normalize per level so indices stay bounded."
• If asked DFS, propose {depth: first_index_seen} map and compute idx - first_index + 1.
• Discuss complexity: O(n) time, O(w) space where w is max level width.

Follow-up Questions#

• DFS solution? Use a hashmap of depth -> first index. Update max with idx - first + 1.
• What if values include null sentinel positions in serialization? Same indexing handles it.
• Maximum width of an N-ary tree? Replace 2i, 2i+1 with k*i + j for j in [0, k).
• Find the level with maximum width? Track depth alongside max value.
• How does this relate to heap arrays? Identical indexing scheme.

Key Takeaways#

• LeetCode 662 is a Medium-difficulty FAANG BFS problem asked at Amazon, Meta, and Microsoft.
• Use the heap-style indexing: left = 2i, right = 2i + 1 with root index 0.
• Normalize indices per level by subtracting the leftmost index — prevents overflow on deep trees.
• Width = rightmost_normalized_index + 1 because indices are 0-based.
• Time complexity O(n), space complexity O(w) where w is maximum level width.
• JavaScript needs BigInt for safety on deep trees; Python integers are unbounded.
• Same pattern underlies heap implementations, segment trees, and Fenwick trees.