Maximum Width of Binary Tree

Given the root of a binary tree, return the maximum width of any level. The width of a level is the number of positions between its leftmost and rightmost non-null nodes inclusive, counting the null gaps between them as if the tree were a complete binary tree (a left child sits at index 2i, a right child at 2i + 1).

The tree is given in level-order (breadth-first), using null for missing children.

Hints

· Stuck? Reveal one nudge at a time.

Index nodes as in a complete binary tree: node i has children 2i and 2i+1.

A level's width is its last index minus its first index plus one — this counts the null gaps.

Normalize each level by subtracting its leftmost index so the indices don't overflow.

Common doubts

Width includes the null gaps between the outermost real nodes, which node counts ignore; the index span captures them.

Indices double each level (~2^depth) and overflow on deep trees; subtracting the level's first index keeps them small without changing any width.

Yes — record the leftmost index at each depth (via a left-first DFS) and maximize idx - first[depth] + 1.

Interview follow-ups

· What an interviewer asks next.

Track the depth alongside the maximum width when you update it.

It assigns each node the exact column it would occupy in a full tree, so index differences equal gap-inclusive distances.

Fun facts

The 2i / 2i+1 indexing is the same scheme used to store a binary heap in a flat array.
Normalizing per level is what lets languages with 64-bit ints handle trees thousands of levels deep.

Asked at

AmazonMicrosoftBloomberg

Frequently Sometimes Occasionally

Example 1

Input: root = [1, 3, 2, 5, 3, null, 9]
Output: 4
The widest level is the last, spanning indices 0..3 (nodes 5, 3, _, 9): width 4.

Example 2

Input: root = [1, 3, 2, 5]
Output: 2
Level 1 has both children, indices 0 and 1: width 2.

Constraints

- The number of nodes is in the range [1, 3000] - -100 <= Node.val <= 100

The width counts the null gaps between the outermost real nodes on a level, so plain node counts won't do. Assign each node the array index it would have in a complete binary tree: root 0, and a node at index i has children 2i and 2i+1. A level's width is then rightmostIndex − leftmostIndex + 1. To keep indices from exploding on deep trees, normalize each level by subtracting its leftmost index.

Prerequisites

Before you start

· Concepts used directly in the solution.

Complete-tree indexing. Node i has children 2i and 2i+1 — the heap array layout.

Level-order BFS. Process one level at a time to read its first and last index.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Definition

“Do null gaps count?”

Yes — width spans from the leftmost to the rightmost real node, including the missing positions between them.

“Could indices overflow?”

On deep trees yes; normalize per level (subtract the leftmost index) to keep them small.

The ideal opening — say it like this

I index nodes as in a complete tree: a node at i has children 2i and 2i+1.

Each level's width is its last index minus its first index plus one; I normalize per level so the indices don't overflow.

Understand the problem

Worked example — tree [1, 3, 2, 5, 3, null, 9]

        1(0)
       /    \
      3(0)   2(1)
     / \       \
    5(0)3(1)   9(3)
level 2 indices: 0, 1, 3 -> width 3 - 0 + 1 = 4
answer: 4

Key observations

1Aha

Index like a complete tree

Children at 2i and 2i+1 encode each node's horizontal position including the empty slots.

2Aha

Width = last - first + 1

The outermost indices on a level, differenced, count the gap-inclusive span.

3Aha

Normalize to avoid overflow

Subtracting each level's leftmost index resets it toward 0, keeping numbers bounded without changing widths.

Brute force vs optimal

	DFS with per-depth first index	BFS with indices
Idea	Record leftmost index per depth; max(idx - first)	Per level, last index - first index + 1
Time	O(n)	O(n)
Space	O(height)	O(n)

Both index like a complete tree and normalize; BFS reads the width most directly. Full code is in the Approaches selector below.

Summary

Key takeaway

Index nodes as in a complete tree (children 2i, 2i+1); a level's width is last index − first index + 1. Normalize per level to avoid overflow. O(n) time.

bfs with (node, idx):
    width = last idx - first idx + 1 on each level
    children get 2*(idx-first) and 2*(idx-first)+1