Maximum Width of a Binary Tree

Use conceptual positions

Run BFS and pretend the tree is embedded in a complete binary tree: a node at index i has children 2i and 2i+1 (or the equivalent zero-based form). For each level, width is last position minus first position plus one, so missing interior nodes are counted correctly. Before processing a level, subtract its first position from every index on that level. This normalization preserves differences while preventing indices from growing exponentially with depth.

Why plain node count fails

Counting nodes at a level ignores gaps, which is precisely what width measures in this problem. Store (node, position) pairs in the queue, capture the first and last normalized positions, and update the answer after the level. Use a wide integer even with normalization if language arithmetic is narrow. BFS visits each node once, giving O(n) time and O(w) queue space, where w is the maximum number of nodes held on a level.