Maximum Width of Binary Tree
Last Updated: March 29, 2026
Understanding the Problem
We need to find the widest level in a binary tree, but "width" here has a specific meaning. It is not just 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.
Imagine the binary tree laid out on a grid where the root is at position 0. Its left child would be at position 0 and its right child at position 1. At the next level, those four possible positions would be 0, 1, 2, 3. The width of a level is rightmost_position - leftmost_position + 1.
So the core challenge is not traversal. It is assigning the right positional index to each node so we can compute the span at each level. If we think of the tree as a complete binary tree and number nodes like a heap (root at index 0, left child at 2i, right child at 2i+1), the positions fall into place naturally.
Key Constraints:
Number of nodes in range [1, 3000]-- With at most 3,000 nodes, we have plenty of room for O(n) or even O(n log n) approaches. The key challenge here is not performance but correctness with positional indexing.-100 <= Node.val <= 100-- Node values are irrelevant for this problem. We only care about tree structure, not values.At least 1 node-- The tree is never empty, so we do not need to handle a null root.Answer fits in 32-bit signed integer-- The width can be large but will not overflow a 32-bit int. However, the positional indices themselves can grow exponentially (up to 2^3000 in the worst case), so we need to handle potential overflow in the indexing scheme.
Approach 1: BFS with Positional Indexing
Intuition
The most natural way to process a tree level by level is BFS. And since we need to compare the leftmost and rightmost positions within each level, processing level by level is exactly what we want.
Here is the key idea. In a complete binary tree, if a node sits at index i (using zero-based heap-style numbering), its left child is at index 2 * i and its right child is at 2 * i + 1. We do not need the tree to actually be complete. We just use this numbering system to assign a virtual position to every node, as if the tree were complete. Then at each level, the width is rightmost_index - leftmost_index + 1.
There is a catch though. If the tree is deep and skewed, indices can grow exponentially large, potentially overflowing even a 64-bit integer. The fix is simple: at each level, normalize the indices by subtracting the leftmost index. Since we only care about the relative distance between the leftmost and rightmost nodes at a level, the absolute values do not matter.
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.
BFS requires a queue that can hold O(n/2) nodes at the widest level. Can we use less space by solving this with DFS instead?
Approach 2: DFS with Positional Indexing
Intuition
Instead of processing level by level with BFS, we can dive depth-first and record the first index we see at each level. As we recurse, every time we visit a node, we know its level and its positional index. If it is the first node we have visited at that level, we record its index as the leftmost. For every subsequent node at that level, we compute the width as currentIndex - leftmostIndex + 1 and update our maximum.
The trick is the same heap-style indexing: left child at 2 * i, right child at 2 * i + 1. And the same overflow prevention: normalize indices by subtracting the leftmost index at each level.
Since DFS visits the left subtree before the right, the first node we encounter at any level is always the leftmost. So we just need a list that stores the first index seen at each depth.
DFS visits the left subtree completely before the right subtree. This means the first time we reach any depth, it is always via the leftmost path. So leftmostIndices[depth] always stores the correct leftmost index for that level. Every subsequent node at the same depth has an index greater than or equal to the leftmost, and the difference gives us the width.
The normalization step is what makes this robust. By subtracting the leftmost index before computing children's indices, we reset the index space at each level. This prevents the exponential growth of indices that would otherwise occur in a deep tree.
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).