Maximum Width of Binary Tree

Hard·Tagstreebfsqueuemath

Problem Statement

Given the `root` of a binary tree, return the maximum width of the given tree. The maximum width of a tree is the maximum width among all levels. The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation. Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.

Examples

Example 1

Input

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

Tree

Output

"4"

Why

The maximum width exists in the third level with length 4 (5, 3, null, 9).

Example 2

Input

root: [1, 3, 2, 5, null, null, 9, 6, null, 7]

Tree

Output

"7"

Why

The maximum width exists in the fourth level with length 7 (6, null, null, null, null, null, 7).

Example 3

Input

root: [1, 3, 2, 5]

Tree

Output

"2"

Why

The maximum width exists in the second level with length 2 (3, 2).

Constraints

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

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

A standard BFS queue stores nodes. But to calculate width with missing null nodes, you need to store the conceptual 'index' of each node as well.

Hint 2

Imagine the binary tree is mapped to an array (like a Heap). If a parent node is at index `i`, its left child is at index `2 * i`, and its right child is at index `2 * i + 1`.

Hint 3

Instead of enqueueing just the node, enqueue a pair/object containing `[node, index]`. The width of a level is simply `(index of last node in queue) - (index of first node in queue) + 1`.

Hint 4

Beware of integer overflow! A tree that is a single straight line down the right side for 100 levels will have an index of `2^100`, destroying your integers. To fix this, normalize the indices on each level by subtracting the index of the first node from all children indices!