Maximum Width of Binary Tree

MediumTreeslevel order

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Given the root of a binary tree, return its **maximum width**. The width of one level is the number of positions between its leftmost and rightmost non-null nodes, inclusive, counting the empty positions in between as if the tree at that depth were a complete binary tree. Put differently, number the positions at each depth as a full binary tree would (a node at position p has children at 2p and 2p + 1). The width of a level is rightmostPosition - leftmostPosition + 1, and the answer is the largest width over all levels. The answer is guaranteed to fit in a signed 32-bit integer. Aim for O(n) time with a level-order traversal.

Examples

Input: root = [1,3,2,5,3,null,9]
Output: 4
The bottom level spans 5, 3, (empty), 9, a width of 4.
Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
The deepest level runs from 6 on the far left to 7 on the far right, covering 7 positions.
Input: root = [1,3,2,5]
Output: 2
The second level (3, 2) has width 2; the third level has only 5.

Constraints

  • 1 <= number of nodes <= 3000
  • -100 <= Node.val <= 100
  • The answer fits in a signed 32-bit integer

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More level order problems