Maximum Width of Binary Tree

medium bfs tree

Problem

Treat the tree as a heap-indexed array. Return the largest width across all levels, counting nulls between the leftmost and rightmost non-null nodes.

Inputroot = [1,3,2,5,3,null,9]

Output4

Level 2 spans [5,3,_,9] of width 4.

input

def width_of_tree(root):
    from collections import deque
    q = deque([(root, 0)]); best = 0
    while q:
        first = q[0][1]; last = q[-1][1]; best = max(best, last - first + 1)
        for _ in range(len(q)):
            n, i = q.popleft()
            if n.left: q.append((n.left, 2 * (i - first)))
            if n.right: q.append((n.right, 2 * (i - first) + 1))
    return best

function widthOfBinaryTree(root) {
  let q = [[root, 0]]; let best = 0;
  while (q.length) {
    const first = q[0][1], last = q[q.length - 1][1];
    best = Math.max(best, last - first + 1);
    const nx = [];
    for (const [n, i] of q) {
      if (n.left) nx.push([n.left, 2 * (i - first)]);
      if (n.right) nx.push([n.right, 2 * (i - first) + 1]);
    }
    q = nx;
  }
  return best;
}

int widthOfBinaryTree(TreeNode root) {
    Deque q = new ArrayDeque<>(); q.add(new Object[]{root, 0L}); long best = 0;
    while (!q.isEmpty()) {
        long first = (long) q.peekFirst()[1], last = (long) q.peekLast()[1];
        best = Math.max(best, last - first + 1);
        int sz = q.size();
        for (int k = 0; k < sz; k++) {
            Object[] cur = q.poll(); TreeNode n = (TreeNode) cur[0]; long i = (long) cur[1] - first;
            if (n.left != null) q.add(new Object[]{n.left, 2 * i});
            if (n.right != null) q.add(new Object[]{n.right, 2 * i + 1});
        }
    }
    return (int) best;
}

int widthOfBinaryTree(TreeNode* root) {
    queue> q; q.push({root, 0}); unsigned long long best = 0;
    while (!q.empty()) {
        int sz = q.size(); unsigned long long first = q.front().second, last = first;
        for (int k = 0; k < sz; k++) {
            auto [n, i] = q.front(); q.pop(); last = i; i -= first;
            if (n->left) q.push({n->left, 2 * i});
            if (n->right) q.push({n->right, 2 * i + 1});
        }
        best = max(best, last - first + 1);
    }
    return (int) best;
}

Explanation

Width counts the gaps too, so just counting nodes per level is not enough. The trick is to give every node a heap-style index: if a node has index i, its left child is 2·i and its right child is 2·i + 1, exactly as if the tree were packed into an array.

We do a level-by-level BFS carrying each node's index. For a level, the width is simply last - first + 1, the index of the rightmost node minus the leftmost, plus one. Missing nodes in between are automatically accounted for because their indices are skipped.

One detail keeps the numbers small: at the start of each level we subtract the leftmost index (i - first) before computing children, so indices restart near zero and do not blow up on deep trees.

We keep the maximum width seen across all levels and return it.

Example: [1,3,2,5,3,null,9]. On the bottom level the nodes 5 and 9 sit at indices that span [5, 3, _, 9], a width of 4, which is the answer.

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