Maximum Width of Binary Tree

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

• Width: The number of nodes between the leftmost and rightmost non-null nodes in a level, including the null nodes between them.
• Imagine filling the tree into a complete binary tree structure. We count the distance from Start to End index.

Since we need to count nulls between nodes without actually storing null objects (which would waste memory), we use Indexing Strategy (Heap Indexing).

1. Assign Indices:
   • Root is index 1 (or 0).
   • If node is i, Left Child is 2*i.
   • Right Child is 2*i + 1.
2. BFS: Traverse level by level. Store (Node, Index) pairs in the Queue.
3. Compute Width: For each level, Width = (Last_Index - First_Index) + 1.

Watch how indices grow and how width is computed.