Widest Level of the Tree, Counting the Gaps

Medium25–30 min

Topics

Binary TreeBFSIndexingLevel Order

Companies

AmazonMicrosoftGoogleFacebook

You are given the root of a binary tree. The width of a level is the distance between its leftmost and rightmost nodes, where the empty positions between them are counted too. To make "positions" precise, imagine every node has two child slots, as in a perfect binary tree; the width is the number of slots from the leftmost real node to the rightmost real node, inclusive. Return the largest width over all levels of the tree.

Building every level with explicit empty slots is easy but can explode in size. Numbering the slots (a node in slot s has children in slots 2s and 2s + 1) gives the width from just two numbers per level.

Test Case 1:

Input:root = [8, 5, 12, 2, null, null, 15, 1, null, null, 20]

Output:8

Explanation:On the last level only 1 (far left) and 20 (far right) exist. If every node had two slots, they would occupy the first and the last of the 8 slots that level has room for — a span of 8, gaps included.

Test Case 2:

Input:root = [4, 2, 7, 1, null, null, 9]

Output:4

Explanation:On level 2 the nodes 1 and 9 are at the two extreme slots of a 4-slot row, with two empty slots between them.

Test Case 3:

Input:root = [1]

Output:1

Explanation:A single node has width 1.

Constraints

◆0 ≤ number of nodes ≤ 100; −100 ≤ node.val ≤ 100 (values never affect the answer)
◆The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child
◆The width of a level is the distance from its leftmost node to its rightmost node, counting the empty positions in between, where every node is imagined to have two child slots (as in a complete binary tree). Return the largest width over all levels (0 for an empty tree)
◆The answer is guaranteed to fit in a signed 32-bit integer; use a wider type for intermediate positions

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Expand Each Level With Explicit Empty Slots

Brute

Build each level as a list that includes the empty slots: a real node contributes its two children (missing ones as empty entries), and an empty entry contributes two more empty entries, so the list mirrors the positions of a complete tree. Before expanding, trim the empty entries from both ends of the level; what remains is the level's span, and its length is the width. Continue until a level is entirely empty. This is easy to picture, but the lists can double at every level, so time and space are exponential in the height in the worst case — a two-branch tree only 30 levels deep would need about a billion entries.

TimeO(2^h)

SpaceO(2^h)

Java

Try it out

class Solution {
    public int widestLevel(TreeNode root) {
        if (root == null) return 0;
        List<TreeNode> level = new ArrayList<>();
        level.add(root);
        int best = 0;
        while (!level.isEmpty()) {
            int lo = 0, hi = level.size() - 1;
            while (lo <= hi && level.get(lo) == null) lo++;
            while (hi >= lo && level.get(hi) == null) hi--;
            if (lo > hi) break;
            best = Math.max(best, hi - lo + 1);
            List<TreeNode> next = new ArrayList<>();
            for (int i = lo; i <= hi; i++) {
                TreeNode node = level.get(i);
                next.add(node == null ? null : node.left);
                next.add(node == null ? null : node.right);
            }
            level = next;
        }
        return best;
    }
}

Optimal — Number the Slots and Take Last − First + 1

Optimal

Do not materialize the empty slots — just number them. Give the root slot 0; a node in slot s has children in slots 2s (left) and 2s + 1 (right), exactly like array positions in a complete tree. Process the tree level by level with a queue that carries each node's slot. On a level, the first queued node's slot is the leftmost position; subtract it from every slot on the level (so numbers stay small and never blow up across levels), and the width is (last slot − first slot + 1). Each node is processed once: O(n) time, O(w) queue space. Use a 64-bit type for the slots, because they can grow like 2^depth.

TimeO(n)

SpaceO(n)