Maximum Width of Binary Tree

• Create a queue to store pairs of (TreeNode, Integer) representing the node and its calculated index.
• If the root is null, return 0.
• Add the root node with an initial index of 0 to the queue.
• Initialize a variable maxWidth to 0.
• Loop while the queue is not empty, processing one level at a time:
  • Get the number of nodes on the current level (levelSize).
  • Peek at the first node in the queue to get the starting index for this level (startIdx). This is used for re-basing indices to prevent overflow.
  • Initialize leftmostIdx and rightmostIdx for the current level.
  • Loop levelSize times to process all nodes on the level:
    • Dequeue a (node, index) pair.
    • If it's the first node of the level, store its index in leftmostIdx.
    • If it's the last node of the level, store its index in rightmostIdx.
    • Calculate a relativeIndex = index - startIdx.
    • If the node has a left child, enqueue it with a new index of 2 * relativeIndex + 1.
    • If the node has a right child, enqueue it with a new index of 2 * relativeIndex + 2.
  • After the level is processed, calculate its width as rightmostIdx - leftmostIdx + 1.
  • Update maxWidth with the maximum width found so far.
• Return maxWidth.

We use a queue to perform the level-order traversal. Instead of just storing the tree nodes, we store pairs of (TreeNode, index). The root node is assigned index 0. For any node at index i, its left child would be at 2*i + 1 and its right child at 2*i + 2 in a complete binary tree.

A potential issue is that these indices can grow very large and cause an integer overflow, especially in deep trees. To prevent this, we re-normalize the indices at the beginning of each level. The index of the first node at each level is used as an offset. For any node with an original index p_idx at a level where the leftmost node has index min_idx, its new relative index becomes p_idx - min_idx. The children's indices are then calculated based on this new relative index, which keeps the index values small and manageable.

1// Helper class to store node and its index2class NodeInfo {3    TreeNode node;4    int index;5    NodeInfo(TreeNode node, int index) {6        this.node = node;7        this.index = index;8    }9}10 11class Solution {12    public int widthOfBinaryTree(TreeNode root) {13        if (root == null) {14            return 0;15        }16 17        Queue<NodeInfo> queue = new LinkedList<>();18        queue.offer(new NodeInfo(root, 0));19        int maxWidth = 0;20 21        while (!queue.isEmpty()) {22            int levelSize = queue.size();23            NodeInfo head = queue.peek();24            int startIdx = head.index;25            int leftmostIdx = 0, rightmostIdx = 0;26 27            for (int i = 0; i < levelSize; i++) {28                NodeInfo current = queue.poll();29                TreeNode node = current.node;30                int index = current.index;31 32                if (i == 0) {33                    leftmostIdx = index;34                }35                if (i == levelSize - 1) {36                    rightmostIdx = index;37                }38 39                // Re-base index to prevent overflow40                int relativeIndex = index - startIdx;41 42                if (node.left != null) {43                    // Use long for intermediate calculation to prevent overflow44                    queue.offer(new NodeInfo(node.left, (int)(2L * relativeIndex + 1)));45                }46                if (node.right != null) {47                    queue.offer(new NodeInfo(node.right, (int)(2L * relativeIndex + 2)));48                }49            }50            maxWidth = Math.max(maxWidth, rightmostIdx - leftmostIdx + 1);51        }52        return maxWidth;53    }54}