Maximum Width of Binary Tree

Problem Link

Maximum Width of Binary Tree – LeetCode

Problem: Maximum Width of Binary Tree

Problem Statement

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 leftmost and rightmost non-null nodes at that level,

• including any null nodes in between.

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

Examples

Example 1:

Input: 
        1
       / \
      3   2
     /     \
    5       9
   /         \
  6           7

Output: 8
Explanation: The maximum width is between nodes 6 and 7.

Example 2:

Input: 
       1
      /
     3
    /
   5

Output: 1

Constraints

• The number of nodes in the tree is in the range [1, 3000].

• -100 <= Node.val <= 100

Intuition

We need to measure the width of each level as if the tree were a complete binary tree. To achieve that:

• Track the index of each node as if it were part of a full tree:

  • Left child → 2 * index

  • Right child → 2 * index + 1

• For each level:

  • Store the first and last indices

  • Calculate width = last_index - first_index + 1

Approach

1. Use level-order traversal (BFS) using a Queue.

2. In the queue, store pairs of (node, index):

   • Start indexing from 0 for the root.

3. For each level:

   • Note the index of the first and last node.

   • Compute width = last - first + 1.

   • Update maximum width.

4. Return the maximum width found.

Code (Java)

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

        int maxWidth = 0;
        Queue<Pair<TreeNode, Integer>> q = new LinkedList<>();
        q.offer(new Pair<>(root, 0));

        while (!q.isEmpty()) {
            int size = q.size();
            int min = q.peek().getValue(); // minimum index at current level

            int first = 0, last = 0;

            for (int i = 0; i < size; i++) {
                Pair<TreeNode, Integer> pair = q.poll();
                TreeNode node = pair.getKey();
                int index = pair.getValue() - min; // normalize to avoid overflow

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

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

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

        return maxWidth;
    }
}

Time and Space Complexity

• Time Complexity: O(N)
  Each node is visited once in the level-order traversal.

• Space Complexity: O(N)
  At most, all nodes at the widest level are stored in the queue.

Dry Run

Input Tree:

        1
       / \
      3   2
     /     \
    5       9
   /         \
  6           7

Indexing:

• Root at index 0

• Level 1: 3 (index 0), 2 (index 1)

• Level 2: 5 (index 0), null, null, 9 (index 3)

• Level 3: 6 (index 0), ..., 7 (index 7)

Max width: 7 - 0 + 1 = 8

Conclusion

• This problem cleverly uses complete binary tree indexing to compute true width.

• It’s a great example of combining BFS with positional tracking.

• Ensure index normalization to prevent overflow in deep trees.