Maximum Width of Binary Tree
Understanding the Problem
We need to find the widest level in a binary tree, where "width" has a specific meaning. It is not the count of nodes at a level. It is the distance between the leftmost and rightmost non-null nodes, including any gaps (nulls) in between.
Consider the tree laid out on a grid where the root sits at position 0. Its left child takes position 0 and its right child position 1. At the next level the four possible positions are 0, 1, 2, 3. The width of a level is rightmost_position - leftmost_position + 1.
The challenge is not the traversal. It is assigning each node a positional index so we can measure the span at each level. Numbering nodes the way a binary heap does (root at index 0, left child at 2i, right child at 2i+1) gives every node a position as if the tree were complete, which is what lets us compute the span even when nulls sit between the end nodes.
Key Constraints:
Number of nodes in range [1, 3000]-- An O(n) traversal is more than fast enough. The difficulty is correctness with positional indexing, not speed.-100 <= Node.val <= 100-- Node values do not affect the answer. Only the tree structure matters.At least 1 node-- The tree is never empty, so a null root needs no special handling.Answer fits in 32-bit signed integer-- The final width fits in a 32-bit int. The positional indices do not. In a tree skewed all the way right, the index of the rightmost node at depth d is2^d - 1, which exceeds even a 64-bit integer once d passes 63. The indexing scheme has to keep these indices small, which drives the design of every approach below.
Approach 1: BFS with Positional Indexing
Intuition
BFS processes a tree level by level, which matches what the problem asks for: the leftmost and rightmost positions are compared within a single level.
Assign each node a heap-style index. A node at index i gives its left child index 2 * i and its right child index 2 * i + 1. The tree does not have to be complete; this numbering assigns a virtual position to every node as if it were. At each level the width is then rightmost_index - leftmost_index + 1.
On a deep, skewed tree these indices grow exponentially and overflow even a 64-bit integer. To bound them, normalize at each level by subtracting the leftmost index before computing children. Only the relative distance between the leftmost and rightmost nodes at a level affects the width, so resetting the leftmost to 0 each level changes nothing about the answer while keeping the largest index at any level below the width of that level.
Algorithm
- Create a queue and add the root with index 0.
- While the queue is not empty:
- Record the number of nodes at this level (
levelSize). - Capture the index of the first node in the queue as
leftmost. - Process all nodes at this level, recording the index of the last one as
rightmost. - For each node, enqueue its left child with index
2 * (currentIndex - leftmost)and right child with index2 * (currentIndex - leftmost) + 1. - Update the maximum width as
rightmost - leftmost + 1. - Return the maximum width.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once during the BFS traversal. At each node, we do O(1) work (index computation and enqueue/dequeue).
- Space Complexity: O(n). The queue holds at most one level's worth of nodes. In the worst case (a complete binary tree), the last level has about n/2 nodes.
The BFS queue holds up to O(n) nodes at the widest level. DFS replaces that queue with a recursion stack bounded by the tree height, which is smaller on a balanced tree.
Approach 2: DFS with Positional Indexing
Intuition
DFS reaches the same answer without a queue. Each recursive call carries the node's depth and its heap-style index. The first node visited at a given depth records its index as the leftmost for that depth. Every later node at that depth computes its width as currentIndex - leftmostIndex + 1 and updates the running maximum.
The indexing is the same as in BFS: left child at 2 * i, right child at 2 * i + 1, with indices normalized against the leftmost at each level to prevent overflow.
DFS recurses into the left subtree before the right, so the first node reached at any depth is the leftmost one at that depth. A single list storing the first index seen per depth is enough.
The leftmost-index claim follows from the visit order. DFS finishes the entire left subtree before touching the right subtree, so among all nodes at a given depth, the one reached first lies on the leftmost path and therefore carries the smallest index. Recording that first index as leftmostIndices[depth] is correct, and every later node at the same depth has an index at least as large, so index - leftmostIndices[depth] + 1 is a valid width.
Normalization stays correct because the width depends only on differences of indices at the same level. Subtracting leftmostIndices[depth] before computing a node's children shifts an entire level by a constant, which preserves every pairwise difference one level down while keeping the indices bounded by the level width.
Algorithm
- Create a list
leftmostIndicesto store the first index seen at each depth. - Initialize
maxWidth = 0. - Define a recursive function
dfs(node, depth, index): - If
nodeis null, return. - If
depthequals the size ofleftmostIndices, appendindex(first time visiting this depth). - Compute width as
index - leftmostIndices[depth] + 1. - Update
maxWidthif this width is larger. - Normalize the index:
normalizedIndex = index - leftmostIndices[depth]. - Recurse on left child with
depth + 1and2 * normalizedIndex. - Recurse on right child with
depth + 1and2 * normalizedIndex + 1. - Call
dfs(root, 0, 0). - Return
maxWidth.
Example Walkthrough
Code
- Time Complexity: O(n). We visit every node exactly once during the DFS. At each node, we do O(1) work (index comparison, max update).
- Space Complexity: O(h) where h is the height of the tree. The recursion stack holds at most h frames. For a balanced tree, h = O(log n). For a skewed tree, h = O(n).