STEP 13 · BINARY TREES · HEAP-STYLE INDEXING · MEDIUM

Maximum Width of Binary Tree

WHAT IT SAYS

Find the maximum width across all levels, where width is the distance between a level's leftmost and rightmost nodes — counting the null gaps in between.

WHAT IT'S REALLY ASKING

"The moment nulls count, counting nodes is useless: a level with two nodes can have width two or width two thousand. What you need is each node's ADDRESS — the seat number it would occupy if the tree were complete. And a tree hands out those addresses for free: a child's seat is computable from its parent's."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Pad the tree with placeholder nulls and do BFS

O(2^h) time and space in the worst case — exponential in the depth

Run level-order traversal but keep null children in the queue as placeholders, so each level materialises at its full complete-tree width. Then measure from the first real node to the last real node in each level, and trim trailing nulls to stop the queue exploding.

WHERE THE WORK IS WASTED — The placeholders are the waste, and it is catastrophic rather than proportional: a tree with one long left spine and one long right spine has O(h) real nodes but its bottom level is 2^h seats wide, and the padded queue faithfully materialises every empty seat between them. You are instantiating an exponential amount of NOTHING to measure the distance between two SOMETHINGS — when the distance between two seat numbers is a subtraction.

KEY OBSERVATION — THE UNLOCKlink

Give each node a seat number; width is a subtraction.

Index the tree the way a binary heap indexes an array: the root sits at index 0, and a node at index i has its left child at 2i + 1 and its right child at 2i + 2. Two facts make this the whole solution. First, the numbering is computable top-down in O(1) per node — a child's index is arithmetic on its parent's index, so any traversal can carry it along, and the nulls need never be visited at all. The empty seats exist in the NUMBERING without existing in the walk. Second, the numbering is exactly the geometry the problem asks about. Within one level, the seat indices run left to right in unit steps, one per position of the complete tree — so the width of a level, nulls included, is precisely rightmostIndex - leftmostIndex + 1. The exponential padding of the naive approach was an attempt to materialise this coordinate system physically; the arithmetic version just... uses the coordinates. So: BFS with (node, index) pairs, and per level record the first and last index. BFS is the natural fit because it hands you each level as a contiguous batch — the first element popped in a round is the level's leftmost, the last is its rightmost, no comparisons needed. One real spike remains: the indices themselves. At depth d they reach 2^d, which overflows fixed-width integers long before the node count is any threat. The fix exploits a symmetry — width only ever consumes DIFFERENCES within a level, so the absolute values are irrelevant. Renormalise every level: subtract the level's minimum index from each of its members before computing children. Offsets stay bounded by the level's true width, and the overflow disappears without changing a single answer. (In Python, unbounded integers make this a non-issue; in Java or C++ it is the difference between accepted and wrong answer.)

BFS carrying normalised heap indices

O(n) time — only real nodes visited — O(w) queue space for the widest level's real nodes

Queue holds (node, index) pairs, root at index 0. For each level: snapshot the queue size, record the first and last index popped this round, update the best width with last - first + 1. Push children as (left, 2*(i - base) + 1) and (right, 2*(i - base) + 2), where base is this level's first index. Return the best.

WHAT YOU TRADED — You trade physical structure for a coordinate system: the nulls that the padded BFS materialised become pure arithmetic, at the cost of the renormalisation subtlety that a careless port will omit and a deep skewed tree will punish. The transferable lesson: when a question is about POSITIONS in an idealised complete structure — gaps included — assign complete-tree indices analytically and let subtraction replace materialisation.

WATCH THE IDEA RUN

width = last seat − first seat + 1 0

widest depth —

Counting nodes per level gives the wrong answer — width includes the NULL gaps between the outermost nodes. So we need a ruler, not a tally.

step 1 / 6

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Address the Seats, Skip the Empty Ones

YOU'LL SEE IT AGAIN WHEN

The measure counts positions in an idealised complete structure — gaps and absences included — so counting real elements is provably insufficient.
Each element's position in the idealised structure is O(1) computable from its parent's (heap indexing: 2i+1, 2i+2).
Only differences of positions within a group matter, which licenses per-group renormalisation to dodge overflow.

SAME BLUEPRINT, DIFFERENT PROBLEM

Count Complete Tree NodesVertical Order Traversal (columns as coordinates)Check Completeness of a Binary TreeBinary Heap array representation

The bar isn't "solved it once." It's "could rebuild it from the observation."