Given the root of a binary tree, return the maximum width of the tree. Width is defined as the number of nodes between the leftmost and rightmost non-null nodes in the same level.
Input: root=[1,3,2,5,3,null,9] → Output: 4Input: root=[1,3,2,5,null,null,9,6,null,7] → Output: 7
BFS level-order with position indices. Assign positions: left child = 2*pos, right child = 2*pos+1. Width at each level = (last pos - first pos + 1). Normalize to prevent overflow.
- BFS queue stores (node, position) pairs.
- At each level, width = last - first + 1, normalize by subtracting first position from all.
- Track maximum width.
import java.util.*;
class Solution {
public int widthOfBinaryTree(TreeNode root) {
int max = 0;
Queue<long[]> q = new LinkedList<>(); // [node_addr, position] -- use level-indexed
// Store as queue of TreeNode+position pairs
Deque<Object[]> queue = new ArrayDeque<>();
queue.offer(new Object[]{root, 0L});
while (!queue.isEmpty()) {
int size = queue.size();
long first = 0, last = 0;
for (int i = 0; i < size; i++) {
Object[] pair = queue.poll();
TreeNode node = (TreeNode) pair[0];
long pos = (long) pair[1];
if (i == 0) first = pos;
last = pos;
long norm = pos - first;
if (node.left != null) queue.offer(new Object[]{node.left, 2 * norm});
if (node.right != null) queue.offer(new Object[]{node.right, 2 * norm + 1});
}
max = (int) Math.max(max, last - first + 1);
}
return max;
}
}
- Time Complexity: O(N)
- Space Complexity: O(N)