All problems

Maximum Width of Binary Tree

Medium · tree bfs

You are given the root of a binary tree. Return the width of the widest level of the tree, measured in slots.

To measure a level, picture the tree drawn inside a full binary tree, where level d is a row of 2^d slots and every node keeps the slot it would have in that full tree. The width of a level is the number of slots from its leftmost node to its rightmost node, both included. Empty slots between the two ends count too, even though no node is there. A level with a single node has width 1.

Return the largest width over all levels of the tree.

Examples

Example 1

Input: root = [1, 3, 2, 5, 3, null, 9]

Output: 4

The bottom level has 5 and 3, then an empty slot (the missing child of 2), then 9. From 5 to 9 that is four slots.

Example 2

Input: root = [1, 3, 2, 5]

Output: 2

The second level has two nodes, so its width is 2. The bottom level has a single node, so its width is 1.

Example 3

Input: root = [1, 2, 3, 4, null, null, 5]

Output: 4

On the bottom level 4 is in the first slot and 5 is in the last of four slots. Only two nodes are there, but the two empty slots between them count.

Constraints