Problem Statement

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

The width of a level** is defined as the length between the leftmost and rightmost non-null nodes, considering the null nodes between them in the complete binary tree structure.

If the input tree is empty, return 0.

Example:

Input: [1,3,2,5,3,null,9]
Output: 4
Explanation:
Level 0:        1
Level 1:     3      2
Level 2:   5  3   N   9
Width of level 2 = index(9) - index(5) + 1 = 4

---

Intuition

When we look at a binary tree as if it were a complete binary tree, we can assign indices to each node:

• Root → index 0
• Left child → 2 * parent_index + 1
• Right child → 2 * parent_index + 2

The width of a level = rightmost_index - leftmost_index + 1.

We can use a Breadth-First Search (BFS) approach to traverse level by level while keeping track of each node’s index.

---

Approach: Level Order Traversal (BFS) with Index Tracking

1. Use a queue to perform a BFS.
2. Each element in the queue stores (node, index).
3. For each level:
   • Record the index of the first and last node.
   • Calculate width = last_index - first_index + 1.
   • Keep track of the maximum width.
4. For each node:
   • Assign its left child index = 2 * index + 1
   • Assign its right child index = 2 * index + 2

To prevent overflow in large trees, normalize indices at each level by subtracting the minimum index at that level.

---

Java Solution

import java.util.*;

public class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;

        int maxWidth = 0;
        Queue<Pair<TreeNode, Long>> queue = new LinkedList<>();
        queue.offer(new Pair<>(root, 0L));

        while (!queue.isEmpty()) {
            int size = queue.size();
            long minIndex = queue.peek().getValue();  // To normalize indices
            long first = 0, last = 0;

            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Long> current = queue.poll();
                TreeNode node = current.getKey();
                long index = current.getValue() - minIndex;  // Normalized index

                if (i == 0) first = index;
                if (i == size - 1) last = index;

                if (node.left != null)
                    queue.offer(new Pair<>(node.left, 2 * index + 1));
                if (node.right != null)
                    queue.offer(new Pair<>(node.right, 2 * index + 2));
            }

            int width = (int) (last - first + 1);
            maxWidth = Math.max(maxWidth, width);
        }

        return maxWidth;
    }

    // Simple Pair class (if not using javafx.util)
    private static class Pair<K, V> {
        private K key;
        private V value;
        public Pair(K key, V value) { this.key = key; this.value = value; }
        public K getKey() { return key; }
        public V getValue() { return value; }
    }
}

---

Complexity Analysis

• Time Complexity: O(N), where N is the number of nodes (each node is visited once).
• Space Complexity: O(N), for the queue in BFS traversal.

---

Dry Run

Input Tree:

       1
     /   \
    3     2
   / \     \
  5   3     9

Step-by-step BFS traversal:

Level	Nodes	Index (normalized)	Width Calculation	Max Width
0	[1]	[0]	(0 – 0 + 1) = 1	1
1	[3, 2]	[0, 1]	(1 – 0 + 1) = 2	2
2	[5, 3, 9]	[0, 1, 4]	(4 – 0 + 1) = 5	5

Output: 5

---

Key Insights

1. Assigning indices based on a complete binary tree allows easy width calculation.
2. Normalizing indices at each level prevents integer overflow.
3. This technique of pairing nodes with indices is also useful in other tree-based problems like LeetCode 958 (Check Completeness of a Binary Tree).