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}

• Initialize a member variable maxWidth to 0 and a list leftmostIndices to store the first index encountered at each depth.
• Define a recursive function dfs(node, depth, index).
• Start the process by calling dfs(root, 0, 0L).
• Inside the dfs function:
  • Base case: if node is null, return.
  • If depth equals the size of leftmostIndices, it's the first time we are visiting this level. Since we traverse left-first, this must be the leftmost node. Add its index to leftmostIndices.
  • Calculate the width for the current node's level: width = index - leftmostIndices.get(depth) + 1.
  • Update maxWidth = max(maxWidth, width).
  • Recurse on the left child: dfs(node.left, depth + 1, 2 * index).
  • Recurse on the right child: dfs(node.right, depth + 1, 2 * index + 1).
• Return maxWidth.

The key idea is to maintain a list that stores the index of the leftmost node for each depth. Let's call this leftmostIndices. leftmostIndices.get(d) will hold the index of the first node visited at depth d.

We perform a pre-order traversal (node, then left, then right). This ensures that for any given depth, the first time we visit it, we are at its leftmost node.

To avoid integer overflow with large indices, we use a clever relative indexing scheme. We define the root's index as 0. For a parent node with relative index i, its left child's relative index is 2*i, and its right child's is 2*i + 1. This scheme works because the width calculation rightmost_idx - leftmost_idx + 1 is preserved. The maximum value of the relative index is related to the maximum width, which is guaranteed to fit in a 32-bit integer. However, the intermediate calculations (2*i) can exceed the int range, so we use long for the index parameter to be safe.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    private int maxWidth = 0;6    private List<Long> leftmostIndices;7 8    public int widthOfBinaryTree(TreeNode root) {9        if (root == null) {10            return 0;11        }12        leftmostIndices = new ArrayList<>();13        dfs(root, 0, 0L);14        return maxWidth;15    }16 17    private void dfs(TreeNode node, int depth, long index) {18        if (node == null) {19            return;20        }21 22        // First time visiting this depth, record the leftmost index23        if (depth == leftmostIndices.size()) {24            leftmostIndices.add(index);25        }26 27        // Calculate width for the current level. The difference will fit in an int.28        long currentWidth = index - leftmostIndices.get(depth) + 1;29        maxWidth = Math.max(maxWidth, (int)currentWidth);30 31        // Recurse for children with new relative indices32        dfs(node.left, depth + 1, 2 * index);33        dfs(node.right, depth + 1, 2 * index + 1);34    }35}