• The number of nodes in the tree is in the range [1, 3000]
• -100 <= Node.val <= 100
• Gaps between the outermost nodes of a level count toward its width
• The answer is guaranteed to fit in a 32-bit signed integer

The word "width" is doing something unusual here. It is not how many nodes a level holds — it is how far apart its two outermost nodes are, with the empty seats between them counted. So a level containing two nodes can have a width of eight if those nodes sit at opposite edges of the row.

That immediately rules out the obvious approach. The level-by-level walk from Binary Tree Level Order Traversal gives us each level's nodes, but the missing children were simply skipped when enqueueing, so by the time a level is assembled all information about where the holes were is gone. We need to know each node's horizontal position, not just its membership in a level.

Imagine the tree drawn as a full, gapless row at each depth: depth 0 has one seat, depth 1 has two, depth 2 has four, and depth d has 2^d. Number them so that positions relate simply between parent and child. Give the root position 0; then for a node at position i, put its left child at 2i and its right child at 2i + 1.

This numbering is worth a moment's justification rather than acceptance. Each level's row is twice as long as the one above, and every parent owns exactly two consecutive seats in the row below — the parent at position 0 owns child seats 0 and 1, position 1 owns 2 and 3, position 2 owns 4 and 5. Doubling the parent's index lands on the first of its two owned seats, and adding one lands on the second. So the scheme is exactly "which seat would this node occupy if the level were completely full", which is precisely the coordinate the problem's definition needs. (It is the same indexing that stores a binary heap in a flat array.)

Now the width of a level is arithmetic on positions, and gaps take care of themselves: rightmost position - leftmost position + 1. Nothing needs to know how many nodes are missing, because their seats were already counted by the subtraction.

best, queue = 0, deque([(root, 0)])          # each entry: a node and its seat number
while queue:
    n = len(queue)
    _, first = queue[0]                       # leftmost seat on this level
    last = first
    for _ in range(n):
        node, pos = queue.popleft()
        last = pos                            # the final one seen is the rightmost
        pos -= first                          # rebase, so seats start from 0 again
        if node.left:  queue.append((node.left,  2 * pos))
        if node.right: queue.append((node.right, 2 * pos + 1))
    best = max(best, last - first + 1)
return best

The other detail is that the leftmost node of a level is simply the first one dequeued and the rightmost is the last, which holds because the queue preserves left-to-right order throughout. No sorting or scanning is needed to find the extremes.

The empty seat at position 2 was never enqueued and was never counted explicitly. It was accounted for automatically, because 9's seat number carried the information that something was skipped to its left.

Every node is enqueued and dequeued once, doing constant work: O(N) time, O(W) space for the queue. The positions add a constant per entry.

The transferable move is the one that made the gaps computable: when a problem cares about where things would be rather than what is present, stop tracking the items and start tracking coordinates. Assigning each node a position turned "how many holes are in this level" — a question about absences, which are hard to enumerate — into a subtraction between two present nodes. The same reframing solves Vertical Order Traversal, where each node gets a horizontal coordinate (left child at x - 1, right child at x + 1) so that nodes from different subtrees can be grouped by column. Coordinates let you talk about structure that is not there.