Given the root of a binary tree, return the **## Problem Statement
Given the root of a binary tree, return the maximum width of the tree.
The width of a level is defined as:
Distance between the leftmost
and rightmost non-null nodes
(including null nodes in between).
Brute Force Intuition
In an interview, you can explain it like this:
Perform a level-order traversal and count the number of nodes at each level.
However, this is incorrect because missing (null) nodes between two existing nodes also contribute to the width.
Example:
1
/ \
2 3
/ \
4 5
Level 3 has only two nodes,
but its width is:
4
not 2.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(N)
Moving Towards the Optimal Approach
Treat the binary tree as if it were stored in an array.
Assign every node an index.
Rules:
Root → 0
For every node:
Left Child
↓
2 * index + 1
Right Child
↓
2 * index + 2
Now,
Width of a level becomes:
Last Index
-
First Index
+
1
Pattern Recognition
Whenever you see:
- Width of Binary Tree
- Complete Binary Tree Positioning
Think:
Level Order Traversal + Indexing
Key Observation
Store inside the queue:
(Node, Index)
For every level:
First Index
↓
Last Index
Width:
last - first + 1;
To prevent integer overflow,
normalize indices at every level.
Optimal Approach
Step 1
Perform BFS.
Queue stores:
(Node, Index)
Step 2
For every level,
store:
Minimum Index
Subtract it from every index.
This keeps numbers small.
Step 3
Track:
First Index
↓
Last Index
Step 4
Update answer:
last - first + 1;
Optimal Java Solution
class Pair {
TreeNode node;
int index;
Pair(TreeNode node, int index) {
this.node = node;
this.index = index;
}
}
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0));
int ans = 0;
while (!q.isEmpty()) {
int size = q.size();
int minIndex = q.peek().index;
int first = 0;
int last = 0;
for (int i = 0; i < size; i++) {
Pair curr = q.poll();
int index = curr.index - minIndex;
if (i == 0)
first = index;
if (i == size - 1)
last = index;
if (curr.node.left != null)
q.offer(new Pair(
curr.node.left,
2 * index + 1));
if (curr.node.right != null)
q.offer(new Pair(
curr.node.right,
2 * index + 2));
}
ans = Math.max(ans,
last - first + 1);
}
return ans;
}
}
Dry Run
1
/ \
2 3
/ \
4 5
Assign indices:
0
/ \
1 2
/ \
3 6
Level 1
Indices:
0
Width:
1
Level 2
Indices:
1
2
Width:
2
Level 3
Indices:
3
6
Width:
6 - 3 + 1
=
4
Answer:
4
Why Indexing Works?
The assigned indices represent the positions of nodes in a complete binary tree.
Even if some nodes are missing,
their positions are preserved.
Thus,
Last Index
-
First Index
+
1
correctly measures the actual width.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(N) |
Interview One-Liner
Perform a level-order traversal while assigning complete binary tree indices to each node. The width of each level is the difference between the first and last indices plus one.
Pattern Learned
Level Order
↓
Assign Indices
↓
First Index
↓
Last Index
↓
Maximum Width
Similar Problems
- Maximum Width of Binary Tree
- Complete Binary Tree
- Left View
- Right View
- Vertical Order Traversal
Memory Trick
Think:
Root → 0
↓
Left = 2i + 1
↓
Right = 2i + 2
↓
Width
=
Last - First + 1
Mental Model
BFS
↓
(Node, Index)
↓
Track First & Last
↓
Update Maximum Width
Whenever you hear:
"Maximum Width of Binary Tree"
your brain should immediately think:
Level Order Traversal + Complete Binary Tree Indexing .
The width of a level is defined as:
Distance between the leftmost
and rightmost non-null nodes
(including null nodes in between).
Brute Force Intuition
In an interview, you can explain it like this:
Perform a level-order traversal and count the number of nodes at each level.
However, this is incorrect because missing (null) nodes between two existing nodes also contribute to the width.
Example:
1
/ \
2 3
/ \
4 5
Level 3 has only two nodes,
but its width is:
4
not 2.
Complexity
- Time Complexity: O(N)
- Space Complexity: O(N)
Moving Towards the Optimal Approach
Treat the binary tree as if it were stored in an array.
Assign every node an index.
Rules:
Root → 0
For every node:
Left Child
↓
2 * index + 1
Right Child
↓
2 * index + 2
Now,
Width of a level becomes:
Last Index
-
First Index
+
1
Pattern Recognition
Whenever you see:
- Width of Binary Tree
- Complete Binary Tree Positioning
Think:
Level Order Traversal + Indexing
Key Observation
Store inside the queue:
(Node, Index)
For every level:
First Index
↓
Last Index
Width:
last - first + 1;
To prevent integer overflow,
normalize indices at every level.
Optimal Approach
Step 1
Perform BFS.
Queue stores:
(Node, Index)
Step 2
For every level,
store:
Minimum Index
Subtract it from every index.
This keeps numbers small.
Step 3
Track:
First Index
↓
Last Index
Step 4
Update answer:
last - first + 1;
Optimal Java Solution
class Pair {
TreeNode node;
int index;
Pair(TreeNode node, int index) {
this.node = node;
this.index = index;
}
}
class Solution {
public int widthOfBinaryTree(TreeNode root) {
if (root == null)
return 0;
Queue<Pair> q = new LinkedList<>();
q.offer(new Pair(root, 0));
int ans = 0;
while (!q.isEmpty()) {
int size = q.size();
int minIndex = q.peek().index;
int first = 0;
int last = 0;
for (int i = 0; i < size; i++) {
Pair curr = q.poll();
int index = curr.index - minIndex;
if (i == 0)
first = index;
if (i == size - 1)
last = index;
if (curr.node.left != null)
q.offer(new Pair(
curr.node.left,
2 * index + 1));
if (curr.node.right != null)
q.offer(new Pair(
curr.node.right,
2 * index + 2));
}
ans = Math.max(ans,
last - first + 1);
}
return ans;
}
}
Dry Run
1
/ \
2 3
/ \
4 5
Assign indices:
0
/ \
1 2
/ \
3 6
Level 1
Indices:
0
Width:
1
Level 2
Indices:
1
2
Width:
2
Level 3
Indices:
3
6
Width:
6 - 3 + 1
=
4
Answer:
4
Why Indexing Works?
The assigned indices represent the positions of nodes in a complete binary tree.
Even if some nodes are missing,
their positions are preserved.
Thus,
Last Index
-
First Index
+
1
correctly measures the actual width.
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time Complexity | O(N) |
| Space Complexity | O(N) |
Interview One-Liner
Perform a level-order traversal while assigning complete binary tree indices to each node. The width of each level is the difference between the first and last indices plus one.
Pattern Learned
Level Order
↓
Assign Indices
↓
First Index
↓
Last Index
↓
Maximum Width
Similar Problems
- Maximum Width of Binary Tree
- Complete Binary Tree
- Left View
- Right View
- Vertical Order Traversal
Memory Trick
Think:
Root → 0
↓
Left = 2i + 1
↓
Right = 2i + 2
↓
Width
=
Last - First + 1
Mental Model
BFS
↓
(Node, Index)
↓
Track First & Last
↓
Update Maximum Width
Whenever you hear:
"Maximum Width of Binary Tree"
your brain should immediately think:
Level Order Traversal + Complete Binary Tree Indexing
United States
NORTH AMERICA
Related News
Master Local Fine-Tuning with "gemma-trainer"
8h ago
Building a Plugin-Free Newsletter Popup on WordPress: Custom REST Endpoint Mailchimp API v3
8h ago
ภาษาโปรแกรมมิ่งที่ syntax ง่าย ทำให้ AI หลอนน้อยลง จริงหรือ?
8h ago
How I Built a File-Timestamp-Based Feedback Loop to Enforce AI Output Quality
8h ago
GitHub Trending Digest — 2026-07-07
9h ago