Maximum Width of Binary Tree

1. Introduction and Problem Statement

When studying binary trees, the width of a tree at a specific level is defined as the maximum number of nodes that can exist between any two nodes on that level (inclusive of both boundary nodes, including any hypothetical or missing nodes). The Maximum Width of a Binary Tree is the largest width found across all levels of the tree.

Consider three different binary tree structures:

• Tree 1: A balanced tree where a middle level might have a maximum width of 4.
• Tree 2: A skewed or sparser tree where the maximum width on a level is 2.
• Tree 3: A sparse tree where gaps exist between nodes, yielding a theoretical maximum width of 8 when counting imaginary nodes between leftmost and rightmost real nodes.

Level-by-Level Analysis:
   - Width depends strictly on horizontal node span per level.
   - Bounded by the first node (leftmost) and the last node (rightmost) in that level.

2. Core Mental Model: Tree Indexing

To calculate the width without physically constructing non-existent nodes, we can assign numerical indices to every node in the binary tree, mimicking an array-based representation of a complete binary tree (similar to concepts used in Segment Trees).

If we assign an index $i$ to any given parent node:

• Left Child Index: $2 \times i + 1$ (for 0-based indexing) or $2 \times i$ (for 1-based indexing).
• Right Child Index: $2 \times i + 2$ (for 0-based indexing) or $2 \times i + 1$ (for 1-based indexing).

          Root (Index: 0)
             /       \
   (Left: 2(0)+1=1)   (Right: 2(0)+2=2)
         Node 3           Node 7
         /                    \
   (Left: 2(1)+1=3)     (Right: 2(2)+2=6)

By leveraging this indexing scheme, the width for any given level can be calculated as:

3. The Naive Approach and Its Critical Flaw (Integer Overflow)

If we rigidly follow the standard child indexing formulas ($2i + 1$ and $2i + 2$) down a deep, skewed tree (e.g., a left-skewed or right-skewed tree with $10^5$ nodes), the index value doubles at every single level.

Why It Fails

• The index value grows exponentially ($O(2^n)$).
• In languages like C++ and Java, standard integer limits (INT_MAX or 64-bit bounds) are breached rapidly when depth approaches typical constraints ($N = 10^5$), causing catastrophic numeric overflow.

4. The Optimized Solution: Normalizing Indices Per Level

To prevent exponential integer overflow, we re-index or normalize the nodes at the start of every new level.

How Normalization Works

1. As we process a level using Level Order Traversal (BFS), we identify the minimum index (min) among all nodes present in that specific level.
2. For every node processed in that level, we shift its index by subtracting the minimum index:

3. This forces the leftmost node of every level to always start at index 0 (or 1), keeping index values small, controlled, and completely immune to overflow while perfectly preserving relative distances between nodes.

5. Step-by-Step Algorithm Walkthrough

We implement Breadth-First Search (BFS) using a queue. The queue stores pairs containing:

1. A reference pointer to the TreeNode.
2. The normalized integer index of that node.

Execution Steps

1. Base Case: If the root is null, return 0.
2. Initialization:
   • Initialize ans = 0.
   • Create a Queue storing pair<TreeNode*, int> (or equivalent custom class in Java).
   • Push {root, 0} into the queue.
3. Level Iteration Loop:
   • While the queue is not empty, get the size of the queue (representing the number of nodes at the current level).
   • Capture the index of the first node popped in this level as minId.
   • Track first index and last index as you iterate through the level's nodes.
   • For each node at index currId = current_node_index - minId:
     • If the node has a left child, push {node->left, 2 * currId + 1} into the queue.
     • If the node has a right child, push {node->right, 2 * currId + 2} into the queue.
   • After traversing all nodes in the level, calculate level width: last - first + 1.
   • Update ans = max(ans, last - first + 1).
4. Completion: Return ans.

6. Complete Implementation (C++ and Java)

C++ Implementation

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        if (!root) return 0;
        int maxLen = 0;
        queue<pair<TreeNode*, long long>> q;
        q.push({root, 0});

        while (!q.empty()) {
            int size = q.size();
            long long minId = q.front().second; // Minimum index for normalization
            long long first = 0, last = 0;

            for (int i = 0; i < size; i++) {
                long long currId = q.front().second - minId;
                TreeNode* node = q.front().first;
                q.pop();

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

                if (node->left) {
                    q.push({node->left, currId * 2 + 1});
                }
                if (node->right) {
                    q.push({node->right, currId * 2 + 2});
                }
            }
            maxLen = max(maxLen, (int)(last - first + 1));
        }
        return maxLen;
    }
};

Java Implementation

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

class Pair {
    TreeNode node;
    int num;
    Pair(TreeNode _node, int _num) {
        node = _node;
        num = _num;
    }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
        int maxWidth = 0;
        Queue<Pair> q = new LinkedList<>();
        q.offer(new Pair(root, 0));

        while (!q.isEmpty()) {
            int size = q.size();
            int minId = q.peek().num; // Normalize using the first element's index
            int first = 0, last = 0;

            for (int i = 0; i < size; i++) {
                int currId = q.peek().num - minId;
                TreeNode node = q.peek().node;
                q.poll();

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

                if (node.left != null) {
                    q.offer(new Pair(node.left, currId * 2 + 1));
                }
                if (node.right != null) {
                    q.offer(new Pair(node.right, currId * 2 + 2));
                }
            }
            maxWidth = Math.max(maxWidth, last - first + 1);
        }
        return maxWidth;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of Width: The maximum number of nodes between any two nodes on a specific level, including null/hypothetical nodes.
• Level Order Traversal: BFS is the optimal traversal strategy since width calculations are strictly level-dependent.
• Complete Binary Tree Indexing: Parent index $i$ maps to left child $2i + 1$ and right child $2i + 2$.
• Overflow Prevention: Normalizing indices at each level by subtracting the minimum index (minId) keeps numbers small and prevents exponential integer overflow in skewed trees.
• Width Formula: For any given level, width is calculated reliably as $\text{last} - \text{first} + 1$.
• Optimal Efficiency: The problem can be solved cleanly in $O(N)$ time and $O(N)$ auxiliary space.