Maximum Width of Binary Tree

MediumTrees · BFS · Heap Indexing🧩 Tree BFS (Level Order)LeetCode #662 ↗Updated Oct 30, 2026

Problem

Given the root of a binary tree, return its maximum width. The width of a level is the number of positions from its leftmost to its rightmost non-null node inclusive, counting the null gaps a complete tree would have in between. The answer is guaranteed to fit in a 32-bit signed integer.

Input[1,3,2,5,3,null,9]Output4

Input[1,3,2,5,null,null,9,6,null,7]Output7

Input[1,3,2,5]Output2

1 ≤ nodes ≤ 3000 · -100 ≤ Node.val ≤ 100 · answer fits in a signed 32-bit int

Try it yourself

Java

class Solution {
    public int widthOfBinaryTree(TreeNode root) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Number nodes like a heap: children of position p sit at 2p and 2p+1. A level's width is then just last - first + 1 — and re-basing each level so its first position is 0 stops the numbers from overflowing.

PatternTree BFS (Level Order)

Instinct The answer talks about levels, rows, depth order, "closest to the root" or what you see from a side? Queue the tree and process it one level at a time.

Memory hack Freeze the size, drain the row - read n = queue.size() before the loop and one level never bleeds into the next.

Open the Tree BFS (Level Order) guide →

Approaches

Brute ForceMaterialize Levels with Null Padding

Time O(h · W)Space O(W)

Literally build each level as a list that includes null placeholders: every slot (real or null) contributes two child slots. Trim nulls from both ends so the list spans leftmost to rightmost real node; its length is that level's width. W is the answer itself.

Java

public int widthOfBinaryTree(TreeNode root) {
    List<TreeNode> level = new ArrayList<>();
    level.add(root);
    int best = 0;
    while (!level.isEmpty()) {
        best = Math.max(best, level.size());
        List<TreeNode> next = new ArrayList<>();
        for (TreeNode node : level) { // a null slot still owns two null child slots
            next.add(node == null ? null : node.left);
            next.add(node == null ? null : node.right);
        }
        int lo = 0, hi = next.size() - 1;
        while (lo <= hi && next.get(lo) == null) lo++;
        while (hi >= lo && next.get(hi) == null) hi--;
        level = new ArrayList<>(next.subList(lo, hi + 1)); // trimmed span
    }
    return best;
}

Mirrors the definition exactly, but W can be ~2³¹ slots — memory explodes.

BetterDFS with Positions + First Index per Depth

Time O(n)Space O(h)

Pre-order DFS passing each node's position. Because left is visited before right, the first node seen at a depth is that level's leftmost, so remember its position; every node's width candidate is pos - first[depth] + 1. Children are numbered from the re-based position to keep values small.

Java

public int widthOfBinaryTree(TreeNode root) {
    return dfs(root, 0, 0L, new ArrayList<>());
}
private int dfs(TreeNode node, int depth, long pos, List<Long> first) {
    if (node == null) return 0;
    if (depth == first.size()) first.add(pos); // leftmost node of this depth
    long rel = pos - first.get(depth);          // re-based position, never huge
    int width = (int) (rel + 1);
    width = Math.max(width, dfs(node.left, depth + 1, 2 * rel, first));
    width = Math.max(width, dfs(node.right, depth + 1, 2 * rel + 1, first));
    return width;
}

Linear time and only O(h) extra space, but recursive and the re-basing is subtle.

OptimalBFS with Re-based Heap Indices

Time O(n)Space O(w)

Level-order BFS that stores a position alongside each node. At the start of a level, read the first node's position and subtract it from every node in that level before computing children 2p / 2p+1. The width is the last re-based position + 1.

Java

public int widthOfBinaryTree(TreeNode root) {
    Deque<TreeNode> nodes = new ArrayDeque<>();
    Deque<Long> pos = new ArrayDeque<>();
    nodes.offer(root);
    pos.offer(0L);
    int best = 0;
    while (!nodes.isEmpty()) {
        int size = nodes.size();
        long base = pos.peek(); // leftmost position of this level
        long rel = 0;
        for (int i = 0; i < size; i++) {
            TreeNode node = nodes.poll();
            rel = pos.poll() - base;
            if (node.left != null) { nodes.offer(node.left); pos.offer(2 * rel); }
            if (node.right != null) { nodes.offer(node.right); pos.offer(2 * rel + 1); }
        }
        best = Math.max(best, (int) (rel + 1)); // last node's position + 1
    }
    return best;
}

Linear, iterative and reads like the definition — the go-to answer.

Pro tip

Without re-basing, a path 64+ levels deep overflows even a long; subtracting the level's first index keeps every number ≤ 2 × answer.

At a glance

Level	Approach	Time	Space
Brute Force	Materialize Levels with Null Padding	`O(h · W)`	`O(W)`
Better	DFS with Positions + First Index per Depth	`O(n)`	`O(h)`
Optimal	BFS with Re-based Heap Indices	`O(n)`	`O(w)`

Common pitfalls

Counting only real nodes per level — width includes the null gaps in between.
Raw heap indices (2^depth) overflow on deep, skinny trees — re-base per level.
Measuring from index 0 instead of the level's leftmost node.

Interview tips

Introduce the heap numbering (2p, 2p+1) before writing any code.
Bring up overflow yourself and show the per-level subtraction fix.
Compare BFS O(w) space with DFS O(h) space as a follow-up.

Pattern

BFS + positional (heap) indexing → questions about horizontal distance, gaps or columns between nodes of a level.

My notes saved in this browser