Maximum Width of Binary Tree

Imagine your binary tree is actually a seating chart in a theater.

Row 0 has 1 seat. Row 1 has 2 seats. Row 2 has 4 seats. Row 3 has 8 seats. Every row doubles. This is true whether or not anyone is sitting there — the seats exist regardless.

Now some people show up and sit down. Not everybody. The chart is patchy — a person here, three empty seats, a person there.

For each row, I want you to do exactly one thing:

That number is the row's width. Do that for every row. Tell me the biggest number you got. Done. That's the whole problem.

The important, sneaky thing: empty seats in the middle still count. If row 5 has one person at the far left and one person at the far right and 30 empty seats between them, that row's width is 32, not 2.

But empty seats outside the two people don't count. We measure from person to person, not wall to wall.

That's it. No algorithm words. Just: how far apart are the two outermost people on the most spread-out row?

Here's the trap, and almost everyone falls into it.

You read "maximum width," you think "level order traversal," you feel great, you write BFS, and then you write this:

And it feels so right. Queue size = number of nodes on this level = width, right?

No. Queue size counts people. The problem asks about seats. Those are completely different numbers the moment the tree has holes in it.

And so people flail. They try:

• Padding the tree with fake null nodes → memory explodes on a skewed tree. A 1000-deep tree would need 2¹⁰⁰⁰ fake nodes.
• Recording "gaps" with counters → gets insanely fiddly and breaks on nested holes.
• A boolean array per level → same explosion problem.

Every one of these fails for the same reason: you're trying to materialize the empty space. And empty space, by definition, refuses to be materialized cheaply.

The unlock is realizing you don't have to. You just have to number it.

Let me convince you, not just tell you.

Take a node sitting at position i in its row (counting from 0, left to right, across the full theoretical row including empty seats).

Ask: where do its children sit?

Each of the i seats to its left — occupied or not — has room for exactly 2 children in the next row. So before this node's children begin, there are exactly 2i seats already spoken for. Therefore:

That's not a convention someone invented. That's arithmetic. The row below is literally twice as wide, so positions double.

Why this destroys the problem

Seat numbers are computed from the parent alone. They don't need to know about siblings, cousins, gaps, or anything else. A node at position 47 produces children at 94 and 95 — full stop. It doesn't matter if positions 0 through 93 are a barren wasteland.

The empty seats get numbered for free. You never build them, never store them, never visit them. They exist purely as the integers you skipped.

And then the finish:

That's the whole trick. Everything else is bookkeeping.

Click a node to see the rule with your own eyes

Every circle below is a seat in the perfect theatre. Click one — its two children light up, and the arithmetic appears underneath.

The second observation — the one that separates a pass from a fail

Seat numbers double every level. Row 40 has seat numbers around 2⁴⁰. Row 60 has seat numbers around 2⁶⁰.

Your int dies at 2³¹. Your long dies at 2⁶³. A tree can easily be 100 levels deep.

So a right-leaning tree — root, right, right, right, sixty times — produces a node with seat number 2⁶⁰ − 1, your int wraps to a negative number, and your answer becomes garbage.

But notice: on that right-leaning tree, every single row has exactly one node. Every row's width is 1. The answer is tiny. Only the labels are astronomical.

Which tells you the fix immediately:

This is index normalization, and it is the entire reason this problem is rated Medium-hard instead of Easy.

Watch the overflow happen — and watch it get fixed

This is a right-leaning spine: root, right, right, right… Every level has exactly one node, so the true answer is always 1. Toggle normalization off and watch a 32-bit integer die at depth 31.

Welcome to the Hotel Fibonacci — sorry, Hotel Binaria. 🏨

An infinite hotel. Floor 0 has 1 room. Floor 1 has 2 rooms. Floor 2 has 4 rooms. Every floor down, rooms double. (Yes, the hotel is an upside-down pyramid. The architect was fired. He now works at Google.)

The house rule: when a guest in room i has children, hotel policy assigns them to rooms 2i and 2i+1 on the floor below. Always. It's in the contract. Nobody gets to pick.

The hotel is mostly empty. Guests are scattered. Rooms sit dark and dusty between them.

Enter our hero: Gary, the world's laziest carpet inspector.

Gary's job: for each floor, measure how much carpet needs cleaning. Management's rule is brutally simple — "Clean from the first occupied room to the last occupied room. Everything between them gets cleaned too, even the empty rooms, because guests walk through that hallway."

Gary doesn't clean before the first guest. Gary doesn't clean after the last guest. Gary cleans first guest → last guest, inclusive.

So Gary walks onto a floor, writes down the room number of the first guest, strolls to the far end, writes down the room number of the last guest, subtracts, adds one, and goes back to his nap. He never counts the empty rooms. He never even looks inside them. Subtraction did the counting.

Now the twist 🎬

Gary gets sent to floor 900. He arrives, pulls out his clipboard, and the room number is:

Gary's clipboard is an int. Gary's clipboard catches fire. 🔥

So the hotel manager introduces local floor numbering. On every floor, a bellhop stands at the first occupied room and slaps a sticker on the door that says "ROOM 0." Everything else on that floor gets renumbered relative to that sticker. The guest 5 rooms down is now "room 5," even if her global number has 40 digits.

Does this break the doubling rule? Not even slightly — the bellhop just applies 2i and 2i+1 to the local number when assigning children, and the next floor's bellhop re-stickers again. Distances between guests are perfectly preserved, because shifting everyone on a floor by the same amount doesn't change how far apart they are.

Gary's clipboard survives. Gary keeps his job. Gary continues to not care about empty rooms.

Cast list

Remember Gary. Gary is your friend. Gary is lazy and Gary is correct.

Let's invent this from nothing. Start stupid.

Attempt 0 — "Just count nodes per level"

Dies immediately on [1,3,2,5,null,null,9]. Bottom level has 2 nodes but width 4. The gaps are invisible to us. ❌

Lesson learned: we need to see the gaps.

Attempt 1 — "Fine, let's MAKE the gaps real"

Build a complete tree. Every missing child becomes an actual null placeholder node that we push into the queue. Now the queue holds every seat, occupied or not, and queue.size() is honest.

This works. And then someone hands you a right-skewed tree of 1000 nodes, you try to allocate 2¹⁰⁰⁰ placeholders, and the heat death of the universe arrives before your program does. ❌

Lesson learned: the gaps must be known but never stored. We need a way to talk about a seat without instantiating it.

Attempt 2 — "Give every node an address"

A name for something absent — that's just a number. So: label every node with the seat it occupies in the perfect tree.

Root gets 0. Node at i gives children 2i and 2i+1. Now a gap isn't an object, it's a skipped integer. Nothing gets allocated. The absent seats are absent, but addressable.

Empty rooms counted, zero empty rooms built. ✅

Attempt 3 — "How do I get min and max per level?"

Two options, and they're both worth knowing:

• BFS: process level by level. The queue is naturally in left-to-right order, so the first node you pop on a level is the leftmost and the last one you pop is the rightmost. You don't even need a min/max scan — order gives it to you free.
• DFS (preorder, left before right): the very first time you ever set foot on depth d, you must be at the leftmost node of that depth — because preorder always exhausts left before touching right. So record first[d] on first arrival, and every later node at depth d computes index − first[d] + 1 against it.

Both are O(n). Both correct. (We compare them in section 13.)

Attempt 4 — "My numbers exploded"

Run either on a 60-deep tree. Indices hit 2⁶⁰. int overflows into negative territory. Your width becomes some cursed number like -1073741820. ❌

Stare at it. Ask: what do I actually use these indices for?

Only one thing: subtracting two of them within the same level. Never across levels. Never as an identity. Never as a key. Just subtraction, within a level.

And subtraction is invariant to shifting: (a − c) − (b − c) = a − b.

So: at the start of every level, subtract the leftmost index from everybody on that level. Leftmost becomes 0. Generate children from the shifted value. The next level re-shifts. Indices never grow beyond roughly the true width of the level. ✅

The final algorithm — which now feels inevitable

1. BFS with (node, index) pairs. Root is (root, 0).
2. At each level: snapshot levelSize = queue.size(), and leftMost = queue.peek().index.
3. Pop exactly levelSize nodes. Track the index of the last one popped as rightMost.
4. For each popped node: normalize norm = index − leftMost, push children at 2·norm and 2·norm + 1.
5. maxWidth = max(maxWidth, rightMost − leftMost + 1).

Tree: [1, 3, 2, 5, null, null, 9, 6, null, null, 7]

Seats in the perfect theatre, so you can see the ghosts before we start:

Now the machine, one step at a time. Dashed circles are ghost seats — the algorithm never allocates them, but the subtraction counts them.

Now watch normalization actually save your life

Different tree — a pure right spine:

Without normalization, indices go 0, 1, 3, 7, 15, 31, … 2⁶⁰ − 1. At depth 31 the int wraps negative, and the moment any tree has a real spread at depth, you get garbage.

With normalization, each level has exactly one node, it's the leftmost, so norm = 0, and its child gets index 2·0 + 1 = 1. Next level: leftMost = 1, norm = 0, child gets 1 again. The index oscillates between 0 and 1 forever. Depth 5000? Still fine. Gary's clipboard survives. 🧯

For each line, one question: what disaster happens if we delete it? Click to open each card.

Twelve ways this goes wrong, in rough order of how often they actually happen.

Trigger words in the prompt

• "width," "span," "spread," "distance between the ends"
• "including the null nodes in between" — this phrase alone should make you write 2i / 2i+1 immediately, no thinking required
• "as if the tree were a complete/perfect binary tree"
• "position in the level," "same level," "leftmost and rightmost"

Structural tells

• The answer depends on where nodes are, not just that they exist.
• Missing children matter — a null changes the answer.
• The problem is asking about geometry, not content.

Same family, all solved by "assign numbers instead of following pointers":

And the backup hook, for the overflow half of the problem:

If you remember nothing else from this lesson six months from now, remember Gary refusing to walk into empty rooms, and the bellhop slapping a "ROOM 0" sticker on every floor. Those two images regenerate the entire algorithm from scratch.

The interviewer asks: "Walk me through your approach." Here is the answer, near-verbatim.

That last sentence is free points. It signals you understand the idea is traversal-independent, not that you memorised one implementation.

The three beats, if you forget the script

The whole lesson, compressed to the size of an index card.