Log inSign up
mediumleetcodeNot Started

Maximum Width of Binary Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Trees
Solve on leetcode
Lesson

Problem Statement

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 extending down to that level are also counted into the length calculation.

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

Example 1 · Example 1: Tree with Gap:

Input: root = [1, 3, 2, 5, 3, null, 9] Tree: 1 / \ 3 2 / \ \ 5 3 9
Output: 4
Explanation: Level 2 has nodes at indices 0 (val 5), 1 (val 3), and 3 (val 9). Width is 3 - 0 + 1 = 4 (including virtual null child of 2).

Example 2 · Example 2: Left-Right Gap:

Input: root = [1, 3, 2, 5, null, null, 9, 6, null, 7] Tree: 1 / \ 3 2 / \ 5 9 / \ 6 7
Output: 8
Explanation: At level 3, the span from 6 to 7 covers 8 slots in a complete binary tree.

Constraints:

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

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand 1D array binary heap coordinate mapping in arbitrary binary trees.
  • Prevent 64-bit arithmetic overflow using level normalization.
  • Calculate level width spanning virtual null nodes.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Maximum width including null gaps.
  • End-to-end distance at any level.
  • Complete binary tree coordinate arithmetic.

Algorithmic Decision Tree:

  • Queue stores {node, id}.
  • minId = q.front().id; for each node in level: curId = node.id - minId.
  • push left with 2*curId + 1, right with 2*curId + 2.
  • maxWidth = max(maxWidth, lastId - firstId + 1).

Connected Patterns:

Binary Tree Level Order TraversalComplete Binary Tree InserterCheck Completeness of a Binary Tree

1. DFS with Level Index Map

Intuition

DFS with helper(node, level, id). Map level -> list of indices. Max width is max over all levels of (max(ids) - min(ids) + 1).

When to apply: Basic baseline check.

Algorithm

  1. Step 1: Traverse with DFS, storing heap coordinate id per level.
  2. Step 2: Track minId[level] and maxId[level].
  3. Step 3: Calculate maxId[level] - minId[level] + 1 for each level.
  4. Step 4: Return maximum width found.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8 unordered_map<int, unsigned long long> minId;
9 unsigned long long maxW = 0;
10 void dfs(TreeNode* node, int level, unsigned long long id) {
11 if (!node) return;
12 if (!minId.count(level)) minId[level] = id;
13 maxW = max(maxW, id - minId[level] + 1);
14 dfs(node->left, level + 1, 2 * id);
15 dfs(node->right, level + 1, 2 * id + 1);
16 }
17public:
18 int widthOfBinaryTree(TreeNode* root) {
19 dfs(root, 0, 1);
20 return maxW;
21 }
22};
23
24int main() {
25 // Sample driver execution
26 cout << "Execution completed successfully." << endl;
27 return 0;
28}
29

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(h) — Recursion call stack takes O(h).

2. Standard BFS Queue with Pair (Node, Index)

Intuition

Use a queue of pairs (node, id). For each level, note first id and last id. Width = last - first + 1. Update overall max.

When to apply: Iterative level-by-level queue processing.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Queue stores pairs (node, id). Push (root, 0).
  3. Step 3: For each level: first = queue.front().id, last = queue.back().id.
  4. Step 4: maxW = max(maxW, last - first + 1).
  5. Step 5: Enqueue left with 2*id+1, right with 2*id+2.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int widthOfBinaryTree(TreeNode* root) {
10 if (!root) return 0;
11 unsigned long long maxW = 0;
12 queue<pair<TreeNode*, unsigned long long>> q;
13 q.push({root, 0});
14 while (!q.empty()) {
15 int sz = q.size();
16 unsigned long long first = q.front().second;
17 unsigned long long last = q.back().second;
18 maxW = max(maxW, last - first + 1);
19 for (int i = 0; i < sz; ++i) {
20 auto [node, id] = q.front(); q.pop();
21 if (node->left) q.push({node->left, 2 * id + 1});
22 if (node->right) q.push({node->right, 2 * id + 2});
23 }
24 }
25 return maxW;
26 }
27};
28
29int main() {
30 // Sample driver execution
31 cout << "Execution completed successfully." << endl;
32 return 0;
33}
34

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum level width w.

3. Normalized BFS Queue (Strict Overflow Prevention)

Intuition

Before processing each level, record minId = q.front().id. For each node in the level, normalize its id: curId = id - minId. Children receive 2 * curId + 1 and 2 * curId + 2. This resets coordinates to small numbers at every level, preventing 64-bit overflow.

When to apply: Optimal gold-standard solution for strict 32-bit overflow safety.

Algorithm

  1. Step 1: If root == null return 0.
  2. Step 2: Queue stores pairs (node, id). Push (root, 0).
  3. Step 3: minId = q.front().id.
  4. Step 4: For each node: curId = id - minId. Enqueue left with 2*curId + 1, right with 2*curId + 2.
  5. Step 5: maxW = max(maxW, lastId - firstId + 1). Return maxW.

Normalized BFS Trace for root = [1, 3, 2, 5, null, null, 9]

2 of 2 questions left today
Step 1 / 2
Trace timeline50% explored
Current operationSTEP 1 OF 2
Step 1: Level 0: Node 1 at index 0
Visual state
Values and pointers at this exact step
tree
Root
1 (idx 0)
L
3 (idx 0)
R
2 (idx 1)

Node order shown; add connections to display explicit tree edges.

level 0: 1
Check / comparison
Level 0: width = 1
Decision / next transition
Enqueue left (idx 0) and right (idx 1).
Why this step matters

Step 1: Level 0: Node 1 at index 0. Width = 0 - 0 + 1 = 1. Children get indices: left(3)=0, right(2)=1.

Step 1 / 2
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <algorithm>
5using namespace std;
6
7class Solution {
8public:
9 int widthOfBinaryTree(TreeNode* root) {
10 if (!root) return 0;
11 long long maxW = 0;
12 queue<pair<TreeNode*, long long>> q;
13 q.push({root, 0});
14 while (!q.empty()) {
15 int sz = q.size();
16 long long minId = q.front().second;
17 long long first = 0, last = 0;
18 for (int i = 0; i < sz; ++i) {
19 long long curId = q.front().second - minId;
20 TreeNode* node = q.front().first;
21 q.pop();
22 if (i == 0) first = curId;
23 if (i == sz - 1) last = curId;
24 if (node->left) q.push({node->left, 2 * curId + 1});
25 if (node->right) q.push({node->right, 2 * curId + 2});
26 }
27 maxW = max(maxW, last - first + 1);
28 }
29 return maxW;
30 }
31};
32
33int main() {
34 // Sample driver execution
35 cout << "Execution completed successfully." << endl;
36 return 0;
37}
38

Time & Space Complexity

  • Time complexity: O(n) — Every node visited once.
  • Space complexity: O(w) — Queue holds maximum level width w.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.DFS Level Index MapO(n)O(h)Track minimum index per level during DFS.Large index overflow.
2.Standard BFS QueueO(n)O(w)Queue pairs (node, id); compute difference between ends.Integer overflow on skewed trees.
3.Normalized BFS QueueOptimalO(n)O(w)Subtract minId at each level to reset indices to 0.None. Gold standard.

Common Pitfalls & Crucial Edge Cases

Crucial Edge Cases to Validate:

  • Single node: returns 1.
  • Completely skewed tree: every level has only 1 node, so width is 1.
  • Full binary tree of depth D: max width is 2^(D-1).

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the integer overflow trap: why 2 * i overflows on deep trees, and how i - minIndex solves it.
  2. Confirm that intermediate null nodes count toward width, but trailing null nodes outside the leftmost/rightmost non-null nodes do not.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why does subtracting minId from each node's index at the start of a level preserve the exact width calculation?

Back to DSA Sheet