Maximum Width of Binary Tree
Given the root of a binary tree, return the maximum width of the given tree.
The maximum width of a tree is the maximum width among all levels.
The width of one level is defined as the length between the end-nodes, which are the leftmost and rightmost non-null nodes. The null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.
It is guaranteed that the answer will be in the range of a 32-bit signed integer.
Example 1
1
/ \
3 2
/ \ \
5 3 9Input
root = [1,3,2,5,3,null,9]Output
4The maximum width exists in the third level with length 4 (5,3,null,9).
Example 2
1
/ \
3 2
/ \
5 9
/ /
6 7Input
root = [1,3,2,5,null,null,9,6,null,7]Output
7The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).
Constraints
- The number of nodes in the tree is in the range
[1, 3000]. -100 <= Node.val <= 100
Asked at 8 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.