Maximum Width of Binary Tree

Preserve holes in a sparse level

Traverse breadth first and give every node the index it would have in a complete binary tree. At each level, retain the first and last index observed and compute last - first + 1. This counts empty slots between existing endpoints, unlike a simple queue-size calculation. Normalize by subtracting the first index of the level before deriving children, so deeply skewed trees do not overflow merely because their conceptual complete-tree indices are huge.

State the invariant

All indices on a level are relative positions with the same offset removed, so differences and therefore width are unchanged. Be consistent: with zero-based indices children are 2i+1 and 2i+2; with one-based indices they are 2i and 2i+1. Handle an empty root as width zero. The traversal is O(n) time and uses O(w) space for the BFS queue. A DFS alternative stores the first position seen at each depth, but needs the same normalization care.