The O(n) Club: Maximum Width of Binary Tree: Counting Gaps Like a Pro

The O(n) Club: Maximum Width of Binary Tree—Counting Gaps Like a Pro

⚡ TL;DR

Width isn’t about how many nodes you see—it’s about the full stretch from the leftmost to rightmost places where nodes could exist, including the gaps between them. Brute force: use BFS, slap unique position indices on all nodes like you’re seating guests for the world’s loneliest dinner party.

// Java TL;DR
deque.add(new NodeWithIdx(root, 1));
while (!deque.isEmpty()) {
    // grab head/tail indices for width at each level
}
// Max width = lastIdx - firstIdx + 1

🧠 How Devs Usually Mess This Up

Everyone thinks “width” means “how many nodes are in this row?”—and that’s how you accidentally predict the weather with a sieve. In reality, those invisible nulls between nodes matter: a tree like [1, null, 3, 4] looks skinny, but by real rules, a huge gap means a huge width. If you’re only counting warm bodies, your code flunks sparse trees—then your interviewer has an existential crisis about computer science education.

🔍 What’s Actually Going On

Let’s play “office seating chart”—two employees, ten seats apart, vacant chairs everywhere. The distance between their seats tells you about the potential chaos, not just how many people showed up. Same with trees: think of every node spot as a numbered seat in a full stadium.
For a binary tree: root is seat 1. Left child is parent*2, right child is parent*2+1. Even those empty spaces get numbers. To find the width at any level, go from the first (leftmost) index to the last (rightmost), counting every potential slot. Only way to win is to keep track of these seat numbers.

🛠️ PseudoCode

• Assign positions by level: Stick (node, index) pairs in a queue, root at index 1.
• Process one level at a time: For each row, note the index of the first and last non-null node.
• Width is last-first+1: Gaps? Who cares, count them too.
• Add children with correct indices: Left goes to index*2, right to index*2+1, like a binary parade.
• Normalize indices per level: To avoid giant numbers (and Java int rage quits), subtract the leftmost index from all others on the same level.

💻 The Code

// Java version using a NodeWithIdx helper!
class NodeWithIdx {
    TreeNode node;
    int idx;
    NodeWithIdx(TreeNode node, int idx) {
        this.node = node;
        this.idx = idx;
    }
}
public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int ans = 0;
    Queue
<nodewithidx> queue = new LinkedList<>();
    queue.offer(new NodeWithIdx(root, 1));
    while (!queue.isEmpty()) {
        int size = queue.size();
        int first = queue.peek().idx, last = first;
        for (int i = 0; i < size; i++) {
            NodeWithIdx current = queue.poll();
            int idx = current.idx - first; // Normalize!
            if (i == size - 1) last = current.idx;
            if (current.node.left != null)
                queue.offer(new NodeWithIdx(current.node.left, idx * 2));
            if (current.node.right != null)
                queue.offer(new NodeWithIdx(current.node.right, idx * 2 + 1));
        }
        ans = Math.max(ans, last - first + 1);
    }
    return ans;
}
</nodewithidx>

⚠️ Pitfalls, Traps & Runtime Smacks

• Counting only active nodes: Sparse trees laugh at you. Always use position indices.
• Integer overflow in deep trees: Java will happily wrap to minus numbers if you aren’t normalizing each level.
• Over-trusting symmetry: Some levels might look tight but span a massive index range. Don’t eyeball it—measure!
• Time & Space: BFS visits every node once. Space for queue: worst case is n/2 on the deepest level.

🧠 Interviewer Brain-Tattoo

“Nodes are people. Indices are their chairs. If you count only people, you’ll always miss the empty chair saving your bacon.”