Maximum Width of BT

Medium

Index nodes as if the tree were an array

Problem

Return the maximum width of a binary tree (max nodes between the leftmost and rightmost on a level, counting gaps).

In simple words

Number nodes like a heap (2i, 2i+1); a level's width is the gap between its first and last index.

The idea

Give the root index 0 and its children 2i and 2i+1, then carry those indices through a level-order walk. A level's width is the last index minus the first plus one, which counts the missing nodes without creating them.

The trick

Normalise indices per level by subtracting the first, or they overflow quickly.
Width counts gaps, so the null positions matter.

←→stepspaceplay

1/5

Optimal

timeO(n)spaceO(n)

Fix the level width up front.

1const q = [root], out = [];2while (q.length) {3  const level = [];4  for (let n = q.length; n > 0; n--) {5    const node = q.shift();6    level.push(node.val);7    if (node.left) q.push(node.left);8    if (node.right) q.push(node.right);9  }10  out.push(level);11}

Input

nodes: 6, 5 edges

Memory

levels: —

Output

answer: —

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:: tree = [1,3,2,5,3,null,9]
Output:: 4
Explanation:: The widest level spans 4 positions.

Example 2

Input:: tree = [1,3,2,5]
Output:: 2
Explanation:: Bottom level width is 2.

Example 3

Input:: tree = [1]
Output:: 1
Explanation:: A single node → width 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.