662 · Maximum Width of Binary Tree

Width counts the null nodes too. Two real nodes sitting far apart on the same level — with nothing but missing children between them — still define a wide level, as if the tree were laid out as a complete binary tree with every slot present.

1 — The problem

The width of one level is the distance between its leftmost and rightmost non-null node, measured as if the whole tree were a complete binary tree — i.e. by pretending every node has an index, root at 1 (or 0), left child at 2×i, right child at 2×i + 1, whether or not that child actually exists. The answer is the largest such width over all levels.

This is why the problem is harder than it first looks: a level can be "wide" purely because two real nodes happen to be far-flung leaves several missing generations apart, with nothing but absent children in between. The visualiser's second row below makes that gap literal — it draws the missing slots as dashed, discarded cells sitting right there in the row.

The naive version of this index scheme doubles the index at every level down, which overflows a 32-bit (or even 64-bit) integer for a deep, lopsided tree in a hurry. The fix costs nothing: re-anchor every level to its own first index — subtract the leftmost index of the level from every index in it before computing children. Widths are differences, so they're completely unaffected by where you put the zero point; only the raw magnitude of the numbers changes.

2 — Visualizing the index gaps

Queue<int[]> q = new LinkedList<>(); // {node placeholder, index}q.add(new Object[]{root, 0L});long maxWidth = 0;while (!q.isEmpty()) {    int sz = q.size();    long first = peekIndex(q, 0), last = peekIndex(q, sz - 1);    maxWidth = Math.max(maxWidth, last - first + 1);    for (int i = 0; i < sz; i++) {        var entry = q.poll();        long idx = entry.index - first; // re-anchor to this level        if (entry.node.left  != null) q.add(entry(entry.node.left,  2 * idx));        if (entry.node.right != null) q.add(entry(entry.node.right, 2 * idx + 1));    }}

The bottom row is the level laid out as a complete binary tree would be: real nodes in their true slot, everything else a discarded gap. The last level shown is the one that matters for this example — two real nodes, five missing slots between them, width 7. That's the entire answer to the problem, and it comes from a level with only two actual tree nodes in it.

3 — Complexity and edge cases

• Time: O(n) — every real node is visited once.
• Space: O(w) for the queue, where w is the widest level by node count (not by index span — those can differ enormously, which is the whole point of the problem).
• Overflow: without re-anchoring, a skewed tree of depth d can produce indices near 2^d; re-anchoring every level keeps the live indices bounded by the level's own node count times a small constant, regardless of overall depth.
• A single node: width 1.
• A perfectly balanced tree: width doubles every level, so the answer is simply the node count of the bottom level — the null-gap subtlety never triggers because there are no gaps.
• The interesting case is exactly the one visualised: a level whose real nodes are separated by long stretches of missing descendants elsewhere in the tree.

4 — Reference implementation

public int widthOfBinaryTree(TreeNode root) {
    record Entry(TreeNode node, long index) {}
    if (root == null) return 0;
    Queue<Entry> q = new LinkedList<>();
    q.add(new Entry(root, 0L));
    long maxWidth = 0;
    while (!q.isEmpty()) {
        int sz = q.size();
        long first = q.peek().index();
        long last  = first;
        for (int i = 0; i < sz; i++) {
            Entry e = q.poll();
            long idx = e.index() - first; // re-anchor
            last = e.index();
            if (e.node().left  != null) q.add(new Entry(e.node().left,  2 * idx));
            if (e.node().right != null) q.add(new Entry(e.node().right, 2 * idx + 1));
        }
        maxWidth = Math.max(maxWidth, last - first + 1);
    }
    return (int) maxWidth;
}