Maximum Width of a Binary Tree

Compute the maximum width of a binary tree using level-order position tracking.

binary-tree breadth-first-search queue

Write a function `max_width(root)` that takes the root of a binary tree and returns the maximum width of the tree. The width of a level is defined as the number of nodes between the leftmost and rightmost non-null nodes (inclusive) at that level, with null nodes also counted. The root is at level 0, and its position is 1. For a node at position `pos`, its left child is at position `2*pos` and its right child at `2*pos + 1`. The width of a level is `rightmost_position - leftmost_position + 1`. If the tree is empty, return 0. The function should be efficient, ideally O(n) time and O(n) space.

Constraints

The number of nodes in the tree is at most 10^5. The tree may be empty (root is None). Node values are arbitrary integers. The tree is represented as nested dictionaries: each node is a dict with keys 'val', 'left', 'right'. 'left' and 'right' are either dicts or None.

Example

```python
# Example 1: width 4
#         1
#       /   \
#      3     2
#     / \     \
#    5   3     9
root = {'val': 1, 'left': {'val': 3, 'left': {'val': 5, 'left': None, 'right': None}, 'right': {'val': 3, 'left': None, 'right': None}}, 'right': {'val': 2, 'left': None, 'right': {'val': 9, 'left': None, 'right': None}}}
max_width(root)  # returns 4
```

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use BFS and store each node with its position index. At each level, compute width as (last_position - first_position + 1).

Positions can grow exponentially, so use subtraction of the minimum position at each level to avoid huge integers (though Python ints are unbounded, it's cleaner).

Track the leftmost position in the current level and update the maximum width after processing the level.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.