#662 Maximum Width of Binary Tree

frequently reported atAmazon Bloomberg Google Microsoft Meta

the problem

In plain words

The width of a level is the number of positions from its leftmost node to its rightmost node, counting the empty spots in between as if the tree were complete there. Return the largest width of any level. The answer fits in a 32-bit signed int.

in root = [1,3,2,5,3,null,9]

out 4

Level 2 is 5, 3, (empty), 9 — four positions.

in root = [1,3,2,5,null,null,9,6,null,7]

out 7

Level 3 is 6, five empty spots, then 7.

in root = [1,3,2,5]

out 2

1 ≤ number of nodes ≤ 3000
-100 ≤ Node.val ≤ 100

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTree BFS (level order)

Number the nodes like a heap array: the root is 0, and a node at position p has children at 2p and 2p + 1. A level's width is last − first + 1. Re-base every level so its first position is 0, and the numbers never blow up.

solutions

From brute force to optimal

Store each level including empty spots (nulls), trim nulls at both ends, measure, then build the next level — a gap has two gap children.

level = [root].
Trim leading and trailing nulls; width = last − first + 1.
Next level = left and right of every slot (null → two nulls).
Stop when a level has no real children.

timeO(total width)

Every empty position between the ends is stored and visited — a V-shaped tree of depth 30 has 2³⁰ slots on its last level, with only two real nodes.

spaceO(max width)

The widest level, gaps included.

javajava.util.*

1class Solution {2    public int widthOfBinaryTree(TreeNode root) {3        List<TreeNode> level = new ArrayList<>(List.of(root));   // may hold nulls = gaps4        int best = 0;5        while (!level.isEmpty()) {6            int first = 0, last = level.size() - 1;7            while (level.get(first) == null) first++;              // trim the gaps at both ends8            while (level.get(last) == null) last--;9            best = Math.max(best, last - first + 1);10            List<TreeNode> next = new ArrayList<>();11            boolean any = false;12            for (int i = first; i <= last; i++) {13                TreeNode node = level.get(i);14                next.add(node == null ? null : node.left);         // a gap has two gap children15                next.add(node == null ? null : node.right);16                if (node != null && (node.left != null || node.right != null)) any = true;17            }18            level = any ? next : new ArrayList<>();19        }20        return best;21    }22}

BFS storing (node, position). Subtract the level's first position from every position before computing children.

Offer (root, 0).
Per level: first = position of the first node.
For each polled node: pos −= first; last = pos; children get 2·pos and 2·pos + 1.
best = max(best, last + 1).

timeO(n)

Each node offered and polled once; no work for empty spots.

spaceO(w)

Two queues holding one level of nodes and positions.

javajava.util.*

1class Solution {2    public int widthOfBinaryTree(TreeNode root) {3        Deque<TreeNode> nodes = new ArrayDeque<>();4        Deque<Long> positions = new ArrayDeque<>();   // like a heap array: p's children are 2p and 2p + 15        nodes.offer(root);6        positions.offer(0L);7        long best = 0;8        while (!nodes.isEmpty()) {9            int size = nodes.size();10            long first = positions.peekFirst();        // re-base: this level's first node becomes 011            long last = 0;12            for (int i = 0; i < size; i++) {13                TreeNode node = nodes.poll();14                long pos = positions.poll() - first;   // keeps the numbers small on deep trees15                last = pos;16                if (node.left != null) {17                    nodes.offer(node.left);18                    positions.offer(2 * pos);19                }20                if (node.right != null) {21                    nodes.offer(node.right);22                    positions.offer(2 * pos + 1);23                }24            }25            best = Math.max(best, last + 1);           // width = last − first + 1, and first is 026        }27        return (int) best;28    }29}

in the room

How to say it in the interview

talk track

Explain the numbering with a picture: 0; 0, 1; 0 … 3 — exactly the indices a heap array would use.
Raise the overflow before they do: positions double every level, so re-base each level and use long.
Width per level = last − first + 1; keep the max.

traps

Counting only the real nodes — the empty spots between the two ends count too.
Not re-basing: positions double each level and pass even a long after ~63 levels. (Java's overflow wraps around, so the difference can still come out right by luck — say you re-base instead of relying on that.)
Using the first and last node of the whole queue instead of the current level.

what they ask next

Follow-ups

DFS version?

Pass (depth, position) down and remember the first position seen at each depth; width = position − first[depth] + 1. Pass the re-based position to the children to keep numbers small.

before you submit

Edge cases to test

One node → 1.
A zigzag chain thousands of levels deep: width 1, but un-based positions overflow even a long.
Only the two outermost leaves at depth d: width 2^d with nothing in between.

practise next