Maximum Width of Binary Tree

Problem Statement: Given the level-order representation of a binary tree as input, compute the maximum width of the binary tree. The width of a level is defined as the difference between the positions of the leftmost and rightmost non-null nodes plus one. In other words, if the leftmost node at a level is at index \(L\) and the rightmost is at index \(R\), then the width is \(R - L + 1\). Note that the indices are determined in the same way as in a complete binary tree (using 0-based indexing).

For example, consider the binary tree represented by the level order list:

[1, 3, 2, 5, 3, null, 9]

The maximum width of this tree is 4.

Your task is to build the binary tree from the input and then calculate its maximum width.

inputFormat

The input is provided via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\), representing the number of tokens in the level-order representation of the binary tree.
• The second line contains \(n\) tokens separated by spaces. Each token is either an integer (the value of a node) or the string null representing a missing node.

outputFormat

Output a single integer to standard output (stdout), representing the maximum width of the binary tree.

1
1

1