Maximum Width of Binary Tree

Ishaan S Published 24 Oct, 2026

You are given the root of a binary tree. Picture every level of the tree laid out as if the tree were complete, so that each level d has 2^d slots, and missing nodes still occupy their slots.

The width of a level is the number of slots from its leftmost real node to its rightmost real node, inclusive; empty slots between those two ends count, empty slots outside them do not. Return the largest width over all levels.

The tree is given as a level-order array where null marks a missing child.

Example 1

Input: root = [7,3,9,null,4,6] Output: 2 Why: Level 1 holds 3 and 9 (width 2). On level 2, node 4 sits in slot 1 and node 6 in slot 2, so the width is again 2: the empty slots 0 and 3 lie outside the ends.

Example 2

Input: root = [1,2,3,4,null,null,5,6,null,null,7] Output: 8 Why: The last level has node 6 in slot 0 and node 7 in slot 7, so its width is 8, including the six empty slots between them.

Example 3

Input: root = [4] Output: 1 Why: A single node is a level of width 1.

Constraints

1 <= number of nodes <= 3000
-100 <= Node.val <= 100
The answer fits in a signed 32-bit integer.

Pattern Path · Trees: BFS · problem 94 of 169

Node values are irrelevant. What matters is where each node would sit if the tree were complete.

Number the slots like a heap: if a node is in slot i, its children are in slots 2i and 2i + 1.

Walk the tree level by level. A level's width is last index - first index + 1.

Slot numbers double every level and explode on deep trees. Subtract the level's first index from every index on that level before computing children.

Target: O(n) time, O(w) extra space.

Start simple

Materialise every level as a full array of 2^d slots (with placeholders for missing nodes) and scan it: exponential time and memory on deep, sparse trees.

The key idea

Give every node a position: the root is 0, and a node at position i has children at 2i and 2i + 1. These are exactly the slot numbers the node would have in a complete tree, so the width of a level is simply the difference between the positions of its last and first nodes, plus one. Empty slots never need to be stored.

A breadth-first search visits each level left to right, so the first and last entries in the queue for a level are its two ends.

The catch is size: positions double on every level, so a chain 1000 nodes deep reaches about 2¹⁰⁰⁰. Only differences within a level matter, so before expanding a level subtract the position of its first node from every node on it. Shifting a whole level by the same amount shifts all of its children by the same amount too, leaving every later difference unchanged, while keeping the numbers no larger than twice the widest width seen.

Complexity

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

Python

from collections import deque

class Solution:
    def widthOfBinaryTree(self, root):
        best = 0
        level = deque([(root, 0)])  # (node, slot position within its level)
        while level:
            first = level[0][1]
            last = level[-1][1]
            best = max(best, last - first + 1)
            for _ in range(len(level)):
                node, pos = level.popleft()
                pos -= first  # normalise so positions stay small
                if node.left:
                    level.append((node.left, 2 * pos))
                if node.right:
                    level.append((node.right, 2 * pos + 1))
        return best

JavaScript

var widthOfBinaryTree = function(root) {
  let best = 0;
  let level = [[root, 0]]; // [node, slot position within its level]
  while (level.length > 0) {
    const first = level[0][1];
    const last = level[level.length - 1][1];
    best = Math.max(best, last - first + 1);
    const next = [];
    for (const [node, p] of level) {
      const pos = p - first; // normalise so positions stay small
      if (node.left) next.push([node.left, 2 * pos]);
      if (node.right) next.push([node.right, 2 * pos + 1]);
    }
    level = next;
  }
  return best;
};

What the interviewer is checking

The interviewer wants to see you turn a geometric description into heap-style indexing, and then notice (or be nudged towards) the overflow problem and fix it with per-level normalisation.

Mistakes to avoid

Counting only the real nodes on a level instead of the slots between its two ends.
Letting positions grow unchecked: on a deep chain they overflow fixed-width integers (or become Infinity in JavaScript) unless you renormalise each level.
Counting empty slots to the left of the first node or to the right of the last one.

Follow-ups to expect

Can you do it with DFS instead of BFS? (Record first position per depth.)
Return which level is widest, not just its width. (Track the depth alongside the best.)
What if the width could exceed 64 bits? (Normalise positions, or use big integers.)

In real software

Tree-drawing tools compute the horizontal extent of each level in the same way to decide how much canvas a layout needs, and heap-style indexing is how binary heaps and segment trees are stored in flat arrays.

Practice next

import java.util.*;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        return 0;
    }
}

public class Main {
    // Builds a tree from a level-order array (null = missing child).
    static TreeNode build(Integer[] a) {
        if (a.length == 0 || a[0] == null) return null;
        TreeNode root = new TreeNode(a[0]);
        Deque<TreeNode> q = new ArrayDeque<>();
        q.add(root);
        int i = 1;
        while (!q.isEmpty() && i < a.length) {
            TreeNode n = q.poll();
            if (i < a.length && a[i] != null) { n.left = new TreeNode(a[i]); q.add(n.left); }
            i++;
            if (i < a.length && a[i] != null) { n.right = new TreeNode(a[i]); q.add(n.right); }
            i++;
        }
        return root;
    }

public static void main(String[] args) {
        TreeNode root = build(new Integer[]{7, 3, 9, null, 4, 6});
        System.out.println(new Solution().widthOfBinaryTree(root)); // 2
    }
}

#include <bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Builds a tree from a level-order array; INT_MIN marks a missing child.
TreeNode* build(const vector<int>& a) {
    if (a.empty() || a[0] == INT_MIN) return nullptr;
    TreeNode* root = new TreeNode(a[0]);
    queue<TreeNode*> q;
    q.push(root);
    size_t i = 1;
    while (!q.empty() && i < a.size()) {
        TreeNode* n = q.front(); q.pop();
        if (i < a.size() && a[i] != INT_MIN) { n->left = new TreeNode(a[i]); q.push(n->left); }
        i++;
        if (i < a.size() && a[i] != INT_MIN) { n->right = new TreeNode(a[i]); q.push(n->right); }
        i++;
    }
    return root;
}

class Solution {
public:
    int widthOfBinaryTree(TreeNode* root) {
        return 0;
    }
};

int main() {
    const int N = INT_MIN;
    TreeNode* root = build({7, 3, 9, N, 4, 6});
    cout << Solution().widthOfBinaryTree(root) << endl;  // 2
}

Topics #094 #t-tree-bfs BFS Medium Practice Queue Tree