#662
Maximum Width of Binary Tree
Medium BFS with position indexes
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
The width of a level is the distance between its leftmost and rightmost non-null nodes, counting the null gaps in between. Return the maximum width.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: the widest level, counting the gaps between the end nodes.
Why this works: number nodes like a heap (children 2i and 2i+1). Width = last index - first index + 1.
Example: 1 (3 (5, 3), 2 (-, 9))
last level indexes 0, 1, 3 → width 3 - 0 + 1 = 4✦Hints open one at a time
Number nodes like a heap: children of i are 2i and 2i + 1.
Width of a level = last index − first index + 1.
Re-base indexes at each level to stop them growing huge.
↗Approach
BFS storing (node, index). For each level, subtract the first index of the level from every index before computing children, then width = last − first + 1.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public int widthOfBinaryTree(TreeNode root) {
Queue<TreeNode> nodes = new ArrayDeque<>();
Queue<Long> idx = new ArrayDeque<>();
nodes.offer(root);
idx.offer(0L);
int best = 0;
while (!nodes.isEmpty()) {
int size = nodes.size();
long first = idx.peek(), last = first;
for (int i = 0; i < size; i++) {
TreeNode n = nodes.poll();
long p = idx.poll() - first; // re-base to keep numbers small
last = p;
if (n.left != null) { nodes.offer(n.left); idx.offer(2 * p); }
if (n.right != null) { nodes.offer(n.right); idx.offer(2 * p + 1); }
}
best = Math.max(best, (int) last + 1);
}
return best;
}
}!Common mistake
Letting indexes double every level — they overflow on deep skewed trees.
Complexity
- Time: O(n).
- Space: O(w).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon