The widest row, gaps included
Measure the width of a tree's widest level, counting the empty slots between its leftmost and rightmost nodes, by numbering positions as in a heap. About 20 minutes.
Empty places count
The width of a level is the distance from its leftmost node to its rightmost node, counting the empty places in between as if the tree were full. Two nodes on a level that are far apart make the level wide, even though the level contains only two nodes.
To see gaps, give each node the position it would have in a full tree. The root is position 0, and the children of position i are at 2i and 2i plus 1.
idx = 3 left_idx = 2 * idx # 6 right_idx = 2 * idx + 1 # 7
- widest
- 1
Row 1 has one node at position 0. Width 1.
Rebase each row
On a deep tree, positions double at every level, and could overflow a normal integer. Before numbering the children of a row, subtract the first position of the row from all of its positions. This changes nothing about the gaps, since all positions in the row shift equally, but keeps the numbers no larger than the width.
The width of a row is the last position minus the first, plus one. The answer is the largest width over all rows.
width = last_idx - first_idx + 1
A row has nodes at positions 2 and 5. What is its width?
- A4, which is 5 minus 2 plus 1
- B2, the number of nodes
- C3
Show the answer
4, which is 5 minus 2 plus 1. The row spans positions 2, 3, 4 and 5, including the empty places.
Maximum width of a binary tree
Given the root of a binary tree, return the maximum width of any level. The width of a level is the length between its leftmost and rightmost non-empty nodes, where the empty places between them, which would be filled in a full binary tree, are also counted. An empty tree has width 0.
root = [1, 3, 2, 5, null, null, 9, 6, null, 7] → 7
0 ≤ number of nodes ≤ 3,000 · the answer fits in a 53-bit integer, because the tree is at most 50 levels deep