Maximum Width of Binary Tree
Find the widest level of the tree (including nulls between end nodes).
Examples
The last level spans slots 0 to 3, including one empty slot.
The last level spans slots 0 to 6: 6 and 7 with five empty slots between.
The second level, 3 and 2, is widest.
Problem Understanding
Find the maximum width of the binary tree under root, taken over all of its levels.
- Width: The number of nodes between the leftmost and rightmost non-null nodes in a level, including the null nodes between them.
- Imagine filling the tree into a complete binary tree structure. We count the distance from Start to End index.
Algorithm Strategy
Give every node the index it would have in a complete binary tree, and the gaps take care of themselves.
- Indices: the root is
0. A node at indexihas its left child at2iand its right child at2i + 1. Two nodes on a level with indices 0 and 3 have two empty slots between them. - BFS with pairs: the queue holds
(node, index). - Width at the start of a level: the front of the queue holds the smallest index,
first, and the back holds the largest,last. The width islast - first + 1. - Keep indices small: as each node is dequeued, subtract
firstfrom its index before computing its children's. Every level then starts near 0, however deep the tree is.
Interactive Visualization
Every node shows the index it was enqueued with. When a level starts, its slots are laid out beside the tree from first to last — nodes and ∅ gaps alike — and the width is the number of slots. Try Example 2, where the last level has five empty slots between its two nodes.
Dry Run
Tree: [1, 3, 2, 5, 3, null, 9] (LeetCode example 1).
| Level | Queue at start (value, index) | first | last | width | best |
|---|---|---|---|---|---|
| 0 | (1, 0) | 0 | 0 | 1 | 1 |
| 1 | (3, 0), (2, 1) | 0 | 1 | 2 | 2 |
| 2 | (5, 0), (3, 1), (9, 3) | 0 | 3 | 4 | 4 |
Slot 2 on the last level is empty — it is where 2's left child would be — but it lies between the first and last nodes, so it counts. The method returns 4.
Edge Cases & Common Mistakes
Edge Cases:
- Single node: width 1.
- Index size: subtracting
firstkeeps indices below twice the widest level seen so far, and LeetCode guarantees the answer fits in a 32-bit integer — but twice that does not, so Java, C++ and C keep indices in 64-bit integers. Python integers and JavaScript numbers hold them exactly.
Common Mistakes:
- Counting only the non-null nodes on a level. The empty slots between the first and last node are part of the width.
- Measuring the width after the level has been dequeued, when the queue already holds the next level.
Solution Code
BFS with Indexing Normalization.
Maximum Width of Binary Tree Code
1var widthOfBinaryTree = function(root) {2 let best = 0;3 const queue = [[root, 0]];4 let head = 0;5 while (head < queue.length) {6 const size = queue.length - head;7 const first = queue[head][1];8 const last = queue[queue.length - 1][1];9 best = Math.max(best, last - first + 1);10 for (let i = 0; i < size; i++) {11 let [node, index] = queue[head++];12 index -= first;13 if (node.left) {14 queue.push([node.left, 2 * index]);15 }16 if (node.right) {17 queue.push([node.right, 2 * index + 1]);18 }19 }20 }21 return best;22};