Maximum Width of Binary Tree

Share

Given the root of a binary tree, return the maximum width of the tree. Width is defined as the number of nodes between the leftmost and rightmost non-null nodes in the same level.

Example 1
Input: root=[1,3,2,5,3,null,9] → Output: 4
Example 2
Input: root=[1,3,2,5,null,null,9,6,null,7] → Output: 7

Solution Approach

BFS level-order with position indices. Assign positions: left child = 2*pos, right child = 2*pos+1. Width at each level = (last pos - first pos + 1). Normalize to prevent overflow.

  • BFS queue stores (node, position) pairs.
  • At each level, width = last - first + 1, normalize by subtracting first position from all.
  • Track maximum width.
Java
import java.util.*;

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        int max = 0;
        Queue<long[]> q = new LinkedList<>(); // [node_addr, position] -- use level-indexed
        // Store as queue of TreeNode+position pairs
        Deque<Object[]> queue = new ArrayDeque<>();
        queue.offer(new Object[]{root, 0L});
        while (!queue.isEmpty()) {
            int size = queue.size();
            long first = 0, last = 0;
            for (int i = 0; i < size; i++) {
                Object[] pair = queue.poll();
                TreeNode node = (TreeNode) pair[0];
                long pos = (long) pair[1];
                if (i == 0) first = pos;
                last = pos;
                long norm = pos - first;
                if (node.left != null) queue.offer(new Object[]{node.left, 2 * norm});
                if (node.right != null) queue.offer(new Object[]{node.right, 2 * norm + 1});
            }
            max = (int) Math.max(max, last - first + 1);
        }
        return max;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)