Max Width Binary Tree LeetCode 662 Guide

LeetCode 662 Maximum Width of Binary Tree asks you to find the maximum width of a binary tree. The width of a level is defined as the number of nodes between the leftmost and rightmost non-null nodes at that level, including any null nodes that fall between them. For example, if a level has nodes at positions 1 and 5 with nulls at 2, 3, and 4 between them, the width is 5 (positions 1 through 5 inclusive).

This definition of width is what makes the problem non-trivial. A simple BFS that counts non-null nodes per level will undercount because it ignores the null gaps between non-null nodes. The key insight is that width depends on the positional spread of nodes across a level, not just how many nodes exist at that level.

The problem guarantees the number of nodes is between 1 and 3000, and node values are between -100 and 100. The answer is guaranteed to fit in a 32-bit signed integer, though intermediate index values can grow very large for deep trees and require careful overflow handling.

A naive BFS implementation processes nodes level by level and counts how many non-null nodes exist at each level. This approach correctly handles trees where all levels are complete, but it fails as soon as any node is missing in the interior of a level. The width is not the count of non-null nodes — it is the span from the leftmost to the rightmost occupied position.

Consider a tree where the root has only a right child, and that right child has only a right child. At depth 2, there is only one non-null node at the rightmost position. A naive BFS would report width 1. The correct answer is 3, because the rightmost position at depth 2 is index 2 (in 0-indexed heap notation), and the leftmost is index 2 — but at depth 1 the right child is at index 2, and its right child is at index 2*2+2 = 6 at depth 2. The leftmost occupied index is also 6, giving width 1, but intermediate levels show the span effect clearly across different examples.

The correct approach is to assign a positional index to every node — whether present or absent — using the same numbering scheme as a heap array. Once every node carries its positional index, the width at any level is simply the rightmost index minus the leftmost index plus one, regardless of how many null gaps lie between them.

The BFS solution extends the standard level-order traversal by storing each node together with its positional index in the queue. Initialize the queue with the root node at index 0. At the start of each level, record the index of the first node in the queue. Process all nodes at the current level: for each node, enqueue its left child at index 2*i+1 and its right child at index 2*i+2 when they exist. After processing the entire level, compute the width as the last index seen minus the first index recorded plus one.

Track the maximum width across all levels and return it after BFS completes. The time complexity is O(n) because every node is enqueued and dequeued exactly once. The space complexity is O(w) where w is the maximum width of the tree, since the queue holds at most one full level of nodes at a time. In the worst case — a complete binary tree — the last level contains n/2 nodes, giving O(n) space.

The implementation is straightforward with Python's collections.deque or Java's ArrayDeque. The key bookkeeping is capturing the first index at the start of each level and the last index at the end of each level. A clean way to implement this is to process each level in a bounded loop using the current queue size, which naturally separates levels without needing sentinel values.

For a balanced tree of depth d, the maximum index at depth d is 2^(d+1) - 2. For a tree with depth 60, this exceeds 2^61, which overflows a 64-bit signed integer. Even in Python, where integers have arbitrary precision, carrying enormous indices through the entire traversal is wasteful. In Java and C++, overflow silently corrupts the width calculation and produces wrong answers.

The fix is index normalization: at the start of each level, subtract the leftmost index of that level from every index at that level. This shifts all indices so the leftmost node at each level always has index 0. The width calculation remains correct because width = rightmost - leftmost = (rightmost - offset) - (leftmost - offset) + 1 = normalized_rightmost - 0 + 1 = normalized_rightmost + 1. Normalization keeps indices bounded by the width of the level rather than the absolute position in a full tree.

In practice, normalization is done when enqueuing children: when a node at normalized index i enqueues its left child, assign the left child index 2*i+1 relative to the already-normalized parent index. Since each level resets, the indices never grow beyond the level width, which is bounded by n (the total number of nodes). This keeps all index values within safe 32-bit range for any input within the problem constraints.

A DFS approach solves the same problem by performing a pre-order traversal while tracking the current depth and current positional index. Maintain a dictionary or array that records the first index seen at each depth level. When visiting a node at depth d with index i, if no first index has been recorded for depth d yet, store i as the first index for that depth. Then update the maximum width as max(maxWidth, i - firstIndex[d] + 1).

Recurse into the left child with index 2*i+1 and depth d+1, then into the right child with index 2*i+2 and depth d+1. Pre-order traversal ensures the leftmost node at each depth is visited before the rightmost, so the first index stored per depth is always the leftmost index at that depth — exactly what is needed for the width calculation.

The DFS approach uses O(h) space where h is the tree height (call stack depth), versus O(w) for BFS. For a balanced tree, O(h) = O(log n) which is better than BFS. For a skewed tree, O(h) = O(n) which matches BFS worst case. Both approaches have O(n) time complexity. The DFS approach is slightly more compact in code, though the BFS approach is more intuitive for level-oriented problems.

Python BFS implementation uses collections.deque storing (node, index) tuples. At the start of each level iteration, capture the queue length and the first index. Loop that many times: dequeue a node and its index, enqueue children with 2*idx+1 and 2*idx+2 while subtracting the first index of the current level (normalization). After each level, update maxWidth with lastIndex - firstIndex + 1. The complete solution is about 15 lines. Time O(n), space O(w) where w is the maximum width.

Java BFS implementation uses ArrayDeque of int[] arrays where each array holds {node reference as id, index}. Because Java does not allow storing object references alongside primitives directly, a common approach is to use a Queue of a simple Pair class or an int[] with the TreeNode stored separately in a parallel structure. Alternatively, use a Queue<long[]> where the long stores a packed representation — though for this problem a simple Queue<Object[]> storing {TreeNode, Long} suffices. Normalize indices per level to avoid overflow.

Both Python and Java solutions follow the same structure: BFS with (node, index) pairs, level-by-level processing, per-level normalization, and max tracking. The core logic is identical; the difference is syntax and data structure idioms. Index normalization is critical in Java to avoid integer overflow — without it, indices exceed Integer.MAX_VALUE for trees with depth beyond 30.

Maximum Width of Binary Tree belongs to the level-order BFS family. The closest relative is Binary Tree Right Side View (LeetCode 199), which also processes trees level by level — but instead of tracking positional indices, it records the last node seen at each level. Both problems use the same BFS scaffolding of processing one level at a time using the queue size as a loop bound.

Zigzag Level Order Traversal (LeetCode 103) extends basic level-order BFS with a direction flag that alternates between left-to-right and right-to-left collection per level. Maximum Depth of Binary Tree (LeetCode 104) is the simplest level-order problem — just count the number of levels processed. Maximum Width adds the complexity of positional index arithmetic on top of the standard BFS structure.

The width family of problems — maximum width, vertical order traversal, and binary tree columns — all share the pattern of assigning positional coordinates to nodes and querying ranges or extremes. If you are comfortable with BFS index tracking for LeetCode 662, vertical order traversal (LeetCode 987) is a natural next step: it adds a horizontal offset coordinate alongside the level coordinate, requiring a more complex sorting step but using the same index assignment principle.