← DSA Atlas
Dedicated problem page · #662

Maximum Width of Binary Tree

MediumTrees and Binary Search TreesLevel-order BFS with heap-style index numberingBFS assigning positional indices to nodes
Solve on LeetCode ↗
662
MediumTrees and Binary Search TreesBFS assigning positional indices to nodesLevel-order BFS with heap-style index numbering

Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width among all levels. The width of a level is the distance between its leftmost and rightmost non-null nodes, counting the null positions between them as if the tree were a complete binary tree.

Open official problem prompt ↗
In plain English

Find the widest level of the tree, treating missing nodes between real ones as occupied slots.

Picture it like this

Numbering seats in a theater row as if the row were full; the width of a row is the seat number of the rightmost person minus the leftmost person plus one, even if seats between them are empty.

Example
Input
root = [1,3,2,5,3,null,9]
Output
4
Why
On the bottom level, nodes 5, 3, and 9 occupy positions 0, 1, and 3 of a complete tree, giving width 3 - 0 + 1 = 4.
Constraints
The number of nodes is in the range [1, 3000]-100 <= Node.val <= 100
Pattern lesson

See the pattern, then code

Level-order BFS with heap-style index numbering
Recognition clue

Width is measured per level including the gaps from missing nodes, which is exactly the complete-binary-tree indexing rule: a level-order traversal that carries each node's position index.

↗
Trees and Binary Search Trees

Hierarchies, subtree aggregation, path properties, or ordered tree queries.. Number nodes as in an array-backed heap: a node at index i has children at 2i and 2i+1. The width of a level is (last index - first index + 1) on that level, which naturally counts null gaps between the extreme nodes.

New words, made simpleKnow these before the algorithm
Complete-tree index
Position a node would occupy in an array heap: children of i are at 2i and 2i+1.
Level width
last index minus first index plus one on a single level.
Level-order (BFS)
Processing the tree one full depth level at a time using a queue.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Count nodes per level

Wrong: it ignores the null gaps the problem explicitly counts.

Just count how many real nodes are on each level.

Time O(n)Space O(n)
Best choiceBFS with positional indices

Directly encodes the gap-counting rule; clean and optimal.

Assign each node a complete-tree index and compute last-minus-first per level.

Time O(n)Space O(n)
The rule we keep true

Invariant

Every node in the queue is paired with the index it would hold in a complete binary tree, so within a level the indices are strictly increasing left to right.

Why this is correct

Reasoning

Complete-tree indexing places a node's children at 2i and 2i+1, exactly the positions they would have if every ancestor slot were filled. Thus the difference between the extreme indices on a level equals the count of positions spanned, including nulls, which is the definition of width. To keep indices from overflowing in other languages you could re-base each level to start at 0; Python's big integers make that optional.

The algorithm in three movesSay these aloud before coding
1BFS level by level, storing each node paired with its complete-tree index

level3 queue: (5,0),(3,1),(9,3)

2For each level, note the index of the first dequeued node

first=0, last=3

3Push children with indices 2i and 2i+1

width = 3-0+1 = 4

4After processing the level, update the answer with (last index - first index + 1)

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
10
31
22
53
34
95
1 · Read(1,0)
2 · Askwidth?
3 · Update statefirst=0,last=0
4 · Resultwidth 1
Key takeaway

Bottom-level nodes carry indices 0, 1, 3; the null under node 2 leaves index 2 empty.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 1Import deque

    A double-ended queue gives O(1) pops from the front for BFS.

  2. 2
    Lines 9-11Snapshot the level

    Fix the level size and record the first node's index before draining the level.

  3. 3
    Lines 12-17Drain and enqueue children

    Pop each node, tracking its index, and enqueue children at 2i and 2i+1.

  4. 4
    Lines 18Update the max width

    last index (idx) minus first plus one is this level's width.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • Single-node tree returns 1
  • A left-skewed then right-skewed shape that widens deep down
  • Sparse levels where the widest is not the deepest
  • All-left or all-right chains (width stays 1)
!

Common beginner mistakes

  • Counting real nodes instead of spanning indices
  • Reading queue[0] after popping (must capture first before draining)
  • Assigning child indices as i+1 style instead of 2i / 2i+1
  • In fixed-width integer languages, index overflow without re-basing each level
Check your understanding

Why do we index children as 2i and 2i+1 rather than sequentially numbering only the real nodes?

More in Trees and Binary Search Trees

#104Maximum Depth of Binary TreePost-order height aggregation#543Diameter of Binary TreePost-order height with a running best#102Binary Tree Level Order TraversalLevel-by-level BFS#98Validate Binary Search TreeRange-bounded validation#236Lowest Common Ancestor of a Binary TreeBottom-up LCA search#105Construct Binary Tree from Preorder and InorderPreorder root + inorder split