Maximum Width of Binary Tree

Description

662. Maximum Width of Binary Tree

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

The maximum width of a tree is the maximum width among all levels.

The width of one level is defined as the length between the end-nodes (the leftmost and rightmost non-null nodes), where the null nodes between the end-nodes that would be present in a complete binary tree extending down to that level are also counted into the length calculation.

It is guaranteed that the answer will in the range of a 32-bit signed integer.

Example 1:

Input: root = [1,3,2,5,3,null,9]
Output: 4
Explanation: The maximum width exists in the third level with length 4 (5,3,null,9).

Example 2:

Input: root = [1,3,2,5,null,null,9,6,null,7]
Output: 7
Explanation: The maximum width exists in the fourth level with length 7 (6,null,null,null,null,null,7).

Example 3:

Input: root = [1,3,2,5]
Output: 2
Explanation: The maximum width exists in the second level with length 2 (3,2).

Constraints:

• The number of nodes in the tree is in the range [1, 3000].
• -100 <= Node.val <= 100

---

Approach 1: BFS Level-Order Traversal with Index Normalization ($O(N)$ Time, $O(N)$ Space)

Intuition

Treat the tree as a binary heap where if a parent node is assigned index $i$:

• Left child index $=2i+1$
• Right child index $=2i+2$

The width of any level is last_index - first_index + 1.
To prevent integer overflow in deep or skewed trees, normalize indices at the start of each level by subtracting the leftmost node’s index (minIndex) before generating child indices.

import java.util.ArrayDeque;
import java.util.Deque;
 
class Solution {
    private static class Pair {
        TreeNode node;
        int index;
 
        Pair(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }
 
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) return 0;
 
        int maxWidth = 0;
        Deque<Pair> queue = new ArrayDeque<>();
        queue.offer(new Pair(root, 0));
 
        while (!queue.isEmpty()) {
            int size = queue.size();
            int minIndex = queue.peek().index; // Normalize using leftmost index
            int first = 0, last = 0;
 
            for (int i = 0; i < size; i++) {
                Pair curr = queue.poll();
                int currIndex = curr.index - minIndex; // Prevent integer overflow
 
                if (i == 0) first = currIndex;
                if (i == size - 1) last = currIndex;
 
                if (curr.node.left != null) {
                    queue.offer(new Pair(curr.node.left, 2 * currIndex + 1));
                }
                if (curr.node.right != null) {
                    queue.offer(new Pair(curr.node.right, 2 * currIndex + 2));
                }
            }
 
            maxWidth = Math.max(maxWidth, last - first + 1);
        }
 
        return maxWidth;
    }
}
 

Complexity

• Time Complexity: $O(N)$ — Each node is pushed and popped from the queue exactly once.
• Space Complexity: $O(N)$ — Maximum queue size is bounded by the widest level (up to $N/2$ nodes).

---

Approach 2: DFS Traversal with Level First-Index Tracking ($O(N)$ Time, $O(N)$ Space)

Intuition

Traverse the tree using Depth-First Search while maintaining level and node position index. Keep a list firstIndices where firstIndices.get(level) stores the position index of the first (leftmost) node reached at that level.

For each node:

1. If visiting level for the first time (level == firstIndices.size()), record its index.
2. Compute level width using index - firstIndices.get(level) + 1 and update maxWidth.
3. Normalize the index (index - firstIndex) before making recursive calls to prevent index overflow.

import java.util.ArrayList;
import java.util.List;
 
class Solution {
    private int maxWidth = 0;
 
    public int widthOfBinaryTree(TreeNode root) {
        List<Integer> firstIndices = new ArrayList<>();
        dfs(root, 0, 0, firstIndices);
        return maxWidth;
    }
 
    private void dfs(TreeNode node, int level, int index, List<Integer> firstIndices) {
        if (node == null) return;
 
        // Record the leftmost node's index at this level
        if (level == firstIndices.size()) {
            firstIndices.add(index);
        }
 
        int firstIndex = firstIndices.get(level);
        maxWidth = Math.max(maxWidth, index - firstIndex + 1);
 
        // Normalize index to avoid overflow in deep trees
        int normalizedIndex = index - firstIndex;
 
        dfs(node.left, level + 1, 2 * normalizedIndex + 1, firstIndices);
        dfs(node.right, level + 1, 2 * normalizedIndex + 2, firstIndices);
    }
}
 

The main reason for using normalizedIndex is to prevent Integer Overflow (32-bit int overflow) in deep or skewed binary trees.

---

1. The Problem: Exponential Index Growth

When indexing nodes like a binary heap:

• Left child index $=2\times \text{parent\_index}+1$
• Right child index $=2\times \text{parent\_index}+2$

Because child indices double at every level, a right-skewed tree grows exponentially:

• Level 0: Index = $0$
• Level 1: Index = $2$
• Level 2: Index = $6$
• Level 3: Index = $14$
• Level 31: Index exceeds Integer.MAX_VALUE ($\approx 2.14\times 10^9$)

Since the constraints allow up to 3,000 nodes, a tree with a depth of 100 or 1,000 will quickly overflow Java’s 32-bit int into negative numbers, leading to completely incorrect width calculations.

2. Why Normalization Fixes It

We only care about the width of nodes at the same level:

$\text{Width}=\text{last\_index}-\text{first\_index}+1$

If we subtract the level’s minimum index (firstIndex) from every node at that level:

1. **The leftmost node becomes 0**.
2. The relative distance between nodes stays 100% identical.
3. The child indices start back near 0 for the next level ($2\times 0+1=1$), resetting the index growth counter completely!

3. Concrete Example

Suppose at Level 10, the leftmost node has index 1000 and the rightmost node has index 1005:

• Without Normalization:

• Width $=1005-1000+1=6$.

• Children generated for the next level will have huge indices starting around $2\times 1000=2000$.

• With Normalization (currIndex - 1000):

• Leftmost index becomes $1000-1000=0$.

• Rightmost index becomes $1005-1000=5$.

• Width $=5-0+1=6$ (exact same result!).

• Children generated for the next level start at small indices ($2\times 0+1=1$), completely avoiding overflow.

Complexity

• Time Complexity: $O(N)$ — Every node is visited once during traversal.
• Space Complexity: $O(N)$ worst-case recursion stack for a skewed tree ($O(\log N)$ for a balanced tree), plus $O(H)$ space for firstIndices where $H$ is tree height.

---

Easy Memory Rule

“Assign heap indices ($2i+1$, $2i+2$) $\to$ Subtract level min index to avoid overflow $\to$ Width $=\text{last}-\text{first}+1$!”