# LeetCode 662: Maximum Width of Binary Tree

## Problem Restatement

We are given the root of a binary tree.

We need to return the maximum width among all levels of the tree.

The width of a level is measured between the leftmost and rightmost non-null nodes on that level.

However, null nodes between those two endpoints are also counted, as if the tree were placed inside a complete binary tree.

## Input and Output

| Item | Meaning |
|---|---|
| Input | The root of a binary tree |
| Output | Maximum width among all levels |
| Width rule | Count positions between leftmost and rightmost non-null nodes |
| Null rule | Null positions between endpoints are included |
| Guarantee | The answer fits in a 32-bit signed integer |

Example function shape:

```python
def widthOfBinaryTree(root: Optional[TreeNode]) -> int:
    ...
```

## Examples

Consider this tree:

```text
        1
       / \
      3   2
     / \   \
    5   3   9
```

The third level contains:

```text
5, 3, null, 9
```

The leftmost non-null node is `5`.

The rightmost non-null node is `9`.

The null position between `3` and `9` is counted.

So the width of that level is:

```text
4
```

The answer is:

```python
4
```

Another example:

```text
        1
       / \
      3   2
     /     \
    5       9
   /         \
  6           7
```

The fourth level contains:

```text
6, null, null, null, null, null, 7
```

So its width is:

```text
7
```

The answer is:

```python
7
```

## First Thought: Count Nodes Per Level

A first idea is to run BFS and count how many real nodes appear on each level.

But this is not enough.

For example:

```text
  5       9
 /         \
6           7
```

At the bottom level, there are only two real nodes: `6` and `7`.

But the width is not `2`.

The missing null positions between them must be counted.

So we need a way to remember where each node would appear in a complete binary tree.

## Key Insight

Assign each node an index as if it were in a complete binary tree.

Use this indexing rule:

| Node | Index |
|---|---|
| Root | `0` |
| Left child of index `i` | `2 * i` |
| Right child of index `i` | `2 * i + 1` |

Then the width of one level is:

```text
rightmost_index - leftmost_index + 1
```

This works because the index gap automatically counts missing null positions between real nodes.

## Why Index Normalization Helps

If the tree is deep, complete-tree indices can become very large.

Python can handle large integers, but it is still cleaner to normalize indices at every level.

For each level, let:

```python
base = queue[0][1]
```

Then subtract `base` from every index on that level.

This keeps indices small while preserving all differences inside the level.

For example, if a level has indices:

```text
100, 101, 107
```

normalizing by `100` gives:

```text
0, 1, 7
```

The width is still:

```text
7 - 0 + 1 = 8
```

## Algorithm

Use BFS.

Each queue entry stores:

```text
(node, index)
```

Start with:

```python
(root, 0)
```

For each level:

1. Let `level_size` be the number of nodes currently in the queue.
2. Read the first index and last index in the queue.
3. Update the answer with:

```python
last_index - first_index + 1
```

4. Process every node on that level.
5. Normalize its index by subtracting the first index.
6. Push its left child with index `2 * normalized_index`.
7. Push its right child with index `2 * normalized_index + 1`.

Return the largest width found.

## Correctness

The algorithm assigns each node the same relative position it would have in a complete binary tree.

For any level, the leftmost non-null node and rightmost non-null node have indices equal to their complete-tree positions. Every missing node between them would occupy an index between those two values.

Therefore:

```text
rightmost_index - leftmost_index + 1
```

counts exactly the width required by the problem.

BFS processes the tree level by level, so when the algorithm computes a width, the queue contains exactly the non-null nodes on that level.

The algorithm updates the answer using the width of every level. Therefore, after all levels are processed, the answer is the maximum width among all levels.

Index normalization does not change widths because subtracting the same base from every index on one level preserves all index differences.

Thus, the algorithm returns the correct maximum width.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each non-null node is processed once |
| Space | `O(w)` | The queue stores one level at a time |

Here, `n` is the number of nodes, and `w` is the maximum number of real nodes stored in the queue at any level.

## Implementation

```python
from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        answer = 0
        queue = deque([(root, 0)])

        while queue:
            level_size = len(queue)
            first_index = queue[0][1]
            last_index = queue[-1][1]

            answer = max(answer, last_index - first_index + 1)

            for _ in range(level_size):
                node, index = queue.popleft()
                index -= first_index

                if node.left is not None:
                    queue.append((node.left, 2 * index))

                if node.right is not None:
                    queue.append((node.right, 2 * index + 1))

        return answer
```

## Code Explanation

We handle an empty tree first:

```python
if root is None:
    return 0
```

Then we start BFS:

```python
queue = deque([(root, 0)])
```

Each queue item contains a node and its complete-tree index.

At the start of each level, the queue contains exactly the nodes on that level.

```python
level_size = len(queue)
first_index = queue[0][1]
last_index = queue[-1][1]
```

The current level width is:

```python
last_index - first_index + 1
```

So we update the answer:

```python
answer = max(answer, last_index - first_index + 1)
```

Then we process all nodes on this level.

```python
for _ in range(level_size):
```

We normalize the index:

```python
index -= first_index
```

This keeps child indices small.

For the left child:

```python
queue.append((node.left, 2 * index))
```

For the right child:

```python
queue.append((node.right, 2 * index + 1))
```

Finally, after all levels are processed:

```python
return answer
```

## Testing

```python
def run_tests():
    s = Solution()

    # Tree:
    #         1
    #        / \
    #       3   2
    #      / \   \
    #     5   3   9
    root = TreeNode(1)
    root.left = TreeNode(3, TreeNode(5), TreeNode(3))
    root.right = TreeNode(2, None, TreeNode(9))

    assert s.widthOfBinaryTree(root) == 4

    # Tree:
    #         1
    #        / \
    #       3   2
    #      /     \
    #     5       9
    #    /         \
    #   6           7
    root = TreeNode(1)
    root.left = TreeNode(3, TreeNode(5), None)
    root.right = TreeNode(2, None, TreeNode(9))
    root.left.left.left = TreeNode(6)
    root.right.right.right = TreeNode(7)

    assert s.widthOfBinaryTree(root) == 7

    # Single node.
    root = TreeNode(1)

    assert s.widthOfBinaryTree(root) == 1

    # Skewed tree.
    root = TreeNode(1)
    root.right = TreeNode(2)
    root.right.right = TreeNode(3)

    assert s.widthOfBinaryTree(root) == 1

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Standard mixed tree | Checks null positions inside a level |
| Wide sparse level | Confirms missing nodes are counted |
| Single node | Smallest non-empty tree |
| Skewed tree | Width remains `1` on every level |