Maximum Width of Binary Tree

Problem

Return the maximum width of the tree. Width = number of nodes between leftmost and rightmost on same level (including nulls).

Key insight: BFS with position indices. Left child = 2i, right child = 2i+1. Width = rightmost - leftmost + 1.

Approach — BFS with Index

Normalize indices at each level to prevent overflow.

Solutions

// C — BFS with (node, index) pairs

// C++
int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int maxW = 0;
    queue<pair<TreeNode*, unsigned long long>> q;
    q.push({root, 0});
    while (!q.empty()) {
        int sz = q.size();
        auto [_, first] = q.front();
        unsigned long long last = 0;
        for (int i = 0; i < sz; i++) {
            auto [node, idx] = q.front(); q.pop();
            idx -= first; // normalize
            if (i == sz - 1) last = idx;
            if (node->left)  q.push({node->left,  2 * idx});
            if (node->right) q.push({node->right, 2 * idx + 1});
        }
        maxW = max(maxW, (int)(last + 1));
    }
    return maxW;
}

// Java
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int maxW = 0;
    Deque<long[]> q = new ArrayDeque<>(); // [node encoded, index]
    // Use list-based approach
    Queue<Object[]> queue = new LinkedList<>();
    queue.add(new Object[]{root, 0L});
    while (!queue.isEmpty()) {
        int sz = queue.size();
        long first = 0, last = 0;
        for (int i = 0; i < sz; i++) {
            Object[] pair = queue.poll();
            TreeNode node = (TreeNode) pair[0];
            long idx = (long) pair[1];
            if (i == 0) first = idx;
            last = idx - first;
            if (node.left != null)  queue.add(new Object[]{node.left,  2 * last});
            if (node.right != null) queue.add(new Object[]{node.right, 2 * last + 1});
        }
        maxW = (int) Math.max(maxW, last + 1);
    }
    return maxW;
}

// JavaScript
function widthOfBinaryTree(root) {
    if (!root) return 0;
    let maxW = 0;
    let queue = [[root, 0n]];
    while (queue.length) {
        const sz = queue.length;
        const first = queue[0][1];
        let last = 0n;
        const next = [];
        for (const [node, idx] of queue) {
            const norm = idx - first;
            last = norm;
            if (node.left)  next.push([node.left,  2n * norm]);
            if (node.right) next.push([node.right, 2n * norm + 1n]);
        }
        maxW = Math.max(maxW, Number(last) + 1);
        queue = next;
    }
    return maxW;
}

# Python
from collections import deque

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_w = 0
    q = deque([(root, 0)])
    while q:
        sz = len(q)
        _, first = q[0]
        last = 0
        for _ in range(sz):
            node, idx = q.popleft()
            last = idx - first
            if node.left:  q.append((node.left,  2 * last))
            if node.right: q.append((node.right, 2 * last + 1))
        max_w = max(max_w, last + 1)
    return max_w

Complexity

Time: O(n)
Space: O(n)

Key Insight

Normalize (subtract leftmost index) at each level to prevent integer overflow from 2^depth indices.