DSA problem
Maximum Width of Binary Tree
Given the root of a binary tree, return the maximum width of the tree. The width of one level is defined as the length of the range between the leftmost and the rightmost non-null nodes at that level, where missing nodes between them count toward the width (as if the tree were padded into a complete binary tree). The maximum width is the maximum value of this measure across all levels.
The clean way to express the index of each node is the heap-style indexing: if a node has index i, its left child has index 2 * i and its right child has index 2 * i + 1. With this scheme, the width of a level is simply rightmostIndex - leftmostIndex + 1, and we maintain it as we BFS the tree.
The dangerous trap is index overflow. For a left-skewed tree of depth 60 the indices double at every level and quickly blow past 2^63. To keep indices small, we re-anchor at every level: when we start processing a level, we subtract the index of its leftmost node from every node before computing child indices. That guarantees the leftmost index of every level is 0, keeping numbers in a safe range for any reasonable input. In Python and JavaScript we can also use BigInt/arbitrary precision, but the re-anchoring trick is the universally portable fix.
The algorithm visits every node once, so it runs in O(n) time and O(w) extra space for the queue, where w is the maximum width of the tree.
Examples
root = [1,3,2,5,3,null,9]4root = [1,3,2,5,null,null,9,6,null,7]7root = [1,3,2,5]2Constraints
- The number of nodes in the tree is in the range [1, 3000].
- -100 <= Node.val <= 100
- The answer is guaranteed to fit in a 32-bit signed integer.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.