How do you identify the pattern for Maximum Width of Binary Tree?

Look for key signals in the prompt: "maximum width of the tree" indicates The widest level, measured as a span from one end to the other, not as a count of nodes.; "null nodes between the end-nodes are counted" indicates Gaps count, so the level's answer is a range of positions. The gaps are never stored.; "width of one level" indicates The width is per level, so one BFS round is the unit of work..

Maximum Width of Binary Tree

Medium·LeetCode #662 Pro OnlyInterview-Level

LeetCode

Problem Statement

You are given the root of a binary tree. Find its maximum width.

The width of one level is the number of slots from its leftmost real node to its rightmost real node. The empty slots between them count too, as if the level were part of a complete binary tree that keeps going down.

Return the largest width over all levels. The answer always fits in a 32-bit signed integer.

Input

The root of a binary tree. The tree is never empty.

Output

The largest width of any level, as an integer.

Example 1

Input: root = [1, 3, 2, 5, 3, null, 9]

Output: 4

The third level has 5, 3, an empty slot and 9. From 5 to 9 there are 4 slots.

Example 2

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

Output: 7

The level with 6 and 7 reads: 6, five empty slots, then 7. That is 7 slots, so the width is 7.

Example 3

Input: root = [1, 3, 2, 5]

Output: 2

The second level has 3 and 2 side by side, with no gap. Width 2.

Constraints

• The number of nodes is between 1 and 3000.
• −100 ≤ Node.val ≤ 100
• The answer fits in a 32-bit signed integer.

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“maximum width of the tree”

→ The widest level, measured as a span from one end to the other, not as a count of nodes.

“null nodes between the end-nodes are counted”

→ Gaps count, so the level's answer is a range of positions. The gaps are never stored.

“width of one level”

→ The width is per level, so one BFS round is the unit of work.

Approach Complexity Ladder

Brute Force — fill every gap with a placeholderO(2^H)O(2^H)

Keep each level as a full row of slots, with placeholders for missing nodes, then measure from the first real node to the last

Optimal — BFS with heap positions, re-based each levelO(N)O(W)

Give each node a heap-style position (left = 2p, right = 2p + 1); a level's width is its last position − its first position + 1

Brute Force Intuition

Walk the tree level by level and keep every slot, real or empty. A missing node becomes a placeholder, and a placeholder gets two placeholder children. A level's width is then the number of slots from its first real node to its last one.

Recognition rule for this sub-pattern:

Compute something per level: last node (right view), max, average, width.

Remember this · Tree BFS

Trigger

Level order, per-level max/average, right side view, minimum depth, nodes at distance k.

Think

Does the question care about depth / rows rather than paths?

Key question

How many nodes are in the current level (queue size at the start of the level)?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Tree BFS translate into production architectures and low-level memory mechanics.

LLD Architecture