Maximum Width of Binary Tree — Problem & Solution
Maximum Width of Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximum Width of Binary Tree is a medium coding problem on depth-first search, breadth-first search and trees, asked in Amazon, Google, Microsoft and Meta interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Breadth-First Search, Trees
- Asked at: Amazon, Google, Microsoft, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given the root of a binary tree, return its maximum width — the largest width among all its levels.
The width of a level is the number of positions between its leftmost and rightmost non-null nodes, both included, counting the empty slots in between as they would be in a complete binary tree reaching that level.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The widest level is the third: from 5 to 9 it spans four positions (5, 3, an empty slot, 9).
Example 2
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: On the fourth level 6 sits at the far left and 7 at the far right of a span of seven positions; the five empty slots between them count.
Example 3
Input: root = [1,3,2,5]
Output: 2
Explanation: The second level, 3 and 2, has width 2; the third holds only 5.
Constraints
The number of nodes in the tree is in the range [1, 3000]-100 <= Node.val <= 100The answer fits in a 32-bit signed integer
Hints for Maximum Width of Binary Tree
Hint 1
Number the positions as in a heap: the root is 0, and a node at position
ihas children at2iand2i + 1.Hint 2
A level's width is then (last position − first position + 1) — a breadth-first walk gives you each level's first and last node.
Hint 3
Positions double on every level and overflow after ~60 levels even in 64 bits. Subtract each level's first position before computing the children's positions.
How to solve Maximum Width of Binary Tree
Give every node the index it would have in a complete binary tree. Within one level, the width is the difference between the rightmost and leftmost indices plus one, null slots included automatically. Re-basing each level's indices at its leftmost node keeps the numbers small.
Approach
- Start a BFS with
(root, 0). - For each level, let
firstbe the index of its first node andlastthat of its last; updatebest = max(best, last - first + 1). - For every node of the level with index
i, letj = i - firstand enqueue its left child with2jand its right child with2j + 1. - Return
bestafter the last level.
Why it works
In a complete-tree numbering, positions on a level are consecutive integers, so the count of slots between two nodes is the difference of their indices plus one. Subtracting the same first from every index on a level shifts the next level's indices by a constant, which leaves every difference — and so every width — unchanged.
Complexity
- Time —
O(n) - Space —
O(w) for one level, w being the widest level
Pitfalls
- Without re-basing, indices on a deep, skinny tree grow like 2^depth and overflow any fixed-width integer.
- Even after re-basing,
2j + 1can reach about 2^32 on a level whose width is near the limit — compute indices in 64 bits. - Empty slots between the end nodes count; nulls outside them do not.
Reference solution
Python
from typing import Optional
def widthOfBinaryTree(root: Optional[TreeNode]) -> int:
best = 0
level = [(root, 0)]
while level:
first = level[0][1]
best = max(best, level[-1][1] - first + 1)
nxt = []
for node, i in level:
j = i - first
if node.left is not None:
nxt.append((node.left, 2 * j))
if node.right is not None:
nxt.append((node.right, 2 * j + 1))
level = nxt
return bestJava
public static int widthOfBinaryTree(TreeNode root) {
long best = 0;
List<TreeNode> nodes = new ArrayList<>();
List<Long> idx = new ArrayList<>();
nodes.add(root);
idx.add(0L);
while (!nodes.isEmpty()) {
long first = idx.get(0);
best = Math.max(best, idx.get(idx.size() - 1) - first + 1);
List<TreeNode> nn = new ArrayList<>();
List<Long> ni = new ArrayList<>();
for (int k = 0; k < nodes.size(); k++) {
long j = idx.get(k) - first;
TreeNode cur = nodes.get(k);
if (cur.left != null) { nn.add(cur.left); ni.add(2 * j); }
if (cur.right != null) { nn.add(cur.right); ni.add(2 * j + 1); }
}
nodes = nn;
idx = ni;
}
return (int) best;
}C++
int widthOfBinaryTree(TreeNode* root) {
long long best = 0;
vector<pair<TreeNode*, long long>> level = {{root, 0}};
while (!level.empty()) {
long long first = level.front().second;
best = max(best, level.back().second - first + 1);
vector<pair<TreeNode*, long long>> next;
for (auto& p : level) {
long long j = p.second - first;
if (p.first->left) next.push_back({p.first->left, 2 * j});
if (p.first->right) next.push_back({p.first->right, 2 * j + 1});
}
level.swap(next);
}
return (int) best;
}JavaScript
var widthOfBinaryTree = function(root) {
var best = 0;
var nodes = [root], idx = [0];
while (nodes.length > 0) {
var first = idx[0];
best = Math.max(best, idx[idx.length - 1] - first + 1);
var nn = [], ni = [];
for (var k = 0; k < nodes.length; k++) {
var j = idx[k] - first;
if (nodes[k].left !== null) { nn.push(nodes[k].left); ni.push(2 * j); }
if (nodes[k].right !== null) { nn.push(nodes[k].right); ni.push(2 * j + 1); }
}
nodes = nn;
idx = ni;
}
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Breadth-First Search (BFS)