Coding Interview PatternsMaximum Width of Binary Tree
MediumTree Breadth-First Search

Maximum Width of Binary Tree

Explanation & Solution

Practice Problem

Description

Given the root of a binary tree, return the maximum width of the given tree.

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree are also counted into the length calculation.

It is guaranteed that the answer will fit in a 32-bit signed integer.

Examples

Example 1:

```tree

[1, 3, 2, 5, 3, null, 9]

`

Input:root = [1, 3, 2, 5, 3, null, 9]
0
1
1
3
2
2
3
5
4
3
5
null
6
9

Output: 4

Explanation: The maximum width exists at level 2 with nodes [5, 3, null, 9], so the width is 4.

Example 2:

```tree

[1, 3, 2, 5, null, null, 9, 6, null, 7]

`

Input:root = [1, 3, 2, 5, null, null, 9, 6, null, 7]
0
1
1
3
2
2
3
5
4
null
5
null
6
9
7
6
8
null
9
7

Output: 7

Explanation: The maximum width exists at level 3 with nodes [6, null, null, null, null, null, 7], so the width is 7.

Example 3:

```tree

[1, 3, 2, 5]

`

Input:root = [1, 3, 2, 5]
0
1
1
3
2
2
3
5

Output: 2

Explanation: The maximum width exists at level 1 with nodes [3, 2], so the width is 2.

Constraints

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

Approach

Tree Breadth-First Search pattern

1. Handle Empty Tree

  • If root is null, return 0

2. Initialize BFS with Position Tracking

  • Create a queue with the root node and its position index 0n (using BigInt)
  • Track maxWidth starting at 0

3. Process Level by Level

  • For each level:
  • Record the position of the first node (levelStart)
  • Process all nodes in the current level
  • Record the position of the last node (levelEnd)
  • For each node at position pos:
  • Left child gets position 2 * (pos - levelStart) (normalized to prevent overflow)
  • Right child gets position 2 * (pos - levelStart) + 1

4. Calculate Width

  • Width of this level = levelEnd - levelStart + 1
  • Update maxWidth if this level is wider

5. Return Result

  • After BFS completes, return maxWidth

Key Insight

  • We assign index positions as if the tree were a complete binary tree: left child = 2 * pos, right child = 2 * pos + 1
  • The width between two nodes is simply rightmost_pos - leftmost_pos + 1
  • We normalize positions at each level (subtract levelStart) to avoid BigInt overflow on very deep trees
Time
O(n)every node is visited once
Space
O(n)the queue may hold up to an entire level of nodes

Visualization

Input:
DFS Traversal[1, 3, 2, 5, 3, 9]
132539
output0

Press play to start DFS traversal

CurrentIn stackComplete
13 steps

Solution Code

Previous
N-ary Tree Level Order Traversal
Next
Even Odd Tree