noodleProblems/
Maximum Width of Binary Tree
#139

Maximum Width of Binary Tree

AlgorithmmediumTreeDepth First SearchBreadth First SearchBinary Tree

Given the root of a binary tree, return its **maximum width**.

The width of one level is the distance between its leftmost and rightmost *non-null* nodes, counting the null slots that would sit between them as if the tree were a complete binary tree. Formally, if you index nodes as in a heap (a node at index i has children 2i and 2i + 1), a level's width is rightmostIndex - leftmostIndex + 1. The answer is the largest level width.

The tree is given as a level-order array where null marks a missing child: [1, 3, 2, 5, 3, null, 9].

Example cases

  • gap counts
    in root = [1,3,2,5,3,null,9]533129
    out 4
    The bottom level holds 5,3 (under 3) and 9 (under 2's right) at positions 0,1,3 — width 4 including the null gap.
  • full level
    in root = [1,3,2,5,3,9,7]5331927
    out 4
    The bottom level is full: 5,3,9,7 at positions 0..3 — width 4.
  • single
    in root = [1]1
    out 1

Constraints

  • The number of nodes in the tree is in the range [1, 3000].
  • -100 <= Node.val <= 100
Saved
root =
[1,3,2,5,3,null,9]