Maximum Width of Binary Tree in DSA Typescript - Execution Trace

Concept Flow - Maximum Width of Binary Tree

Start at root node

↓

Initialize queue with root and index 0

↓

While queue not empty

↓

For each level: get first and last node indices

↓

Calculate width = last_index - first_index + 1

↓

Update max width if current width is larger

↓

Add children to queue with updated indices

↓

Repeat for next level

↓

Return max width found

We traverse the tree level by level, tracking node positions to find the widest level.

Execution Sample

DSA Typescript

function widthOfBinaryTree(root: TreeNode | null): number {
  if (!root) return 0;
  let maxWidth = 0;
  let queue: [TreeNode, number][] = [[root, 0]];
  while (queue.length) {
    const levelLength = queue.length;
    const firstIndex = queue[0][1];
    const lastIndex = queue[queue.length - 1][1];
    maxWidth = Math.max(maxWidth, lastIndex - firstIndex + 1);
    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift()!;
      if (node.left) queue.push([node.left, 2 * (index - firstIndex)]);
      if (node.right) queue.push([node.right, 2 * (index - firstIndex) + 1]);
    }
  }
  return maxWidth;
}

This code finds the maximum width of a binary tree by level order traversal with index tracking.

Execution Table

Step	Operation	Nodes in Queue (node val, index)	Width Calculation	Max Width	Visual Tree State
1	Initialize queue with root (1,0)	[(1,0)]	Width = 0 - 0 + 1 = 1	1	Level 0: 1
2	Process level 0	[]	Width = 0 - 0 + 1 = 1	1	Level 0: 1
3	Add children of 1: left(2,0), right(3,1)	[(2,0),(3,1)]		1	Level 1: 2, 3
4	Process level 1	[(3,1)]	Width = 1 - 0 + 1 = 2	2	Level 1: 2, 3
5	Add children of 2: left(4,0), right(5,1)	[(3,1),(4,0),(5,1)]		2	Level 2: 4, 5
6	Add children of 3: right(7,3)	[(4,0),(5,1),(7,3)]		2	Level 2: 4, 5, 7
7	Process level 2	[]	Width = 3 - 0 + 1 = 4	4	Level 2: 4, 5, null, 7
8	Add children of 4: none	[]		4	Level 3: none
9	Add children of 5: none	[]		4	Level 3: none
10	Add children of 7: none	[]		4	Level 3: none
11	Queue empty, end	[]		4	Final max width = 4

💡 Queue is empty, all levels processed

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 7	Final
queue	[(1,0)]	[(2,0),(3,1)]	[(4,0),(5,1),(7,3)]	[]	[]
maxWidth	0	1	2	4	4

Key Moments - 3 Insights

Why do we subtract firstIndex from each child's index before pushing to queue?

Subtracting firstIndex normalizes indices to prevent integer overflow and keeps indices small, as shown in steps 5 and 6 where child indices are recalculated relative to firstIndex (execution_table rows 5 and 6).

Why is width calculated as lastIndex - firstIndex + 1?

Because indices start at 0, the width is the distance between last and first plus one node, as seen in step 7 where width = 3 - 0 + 1 = 4 (execution_table row 7).

What happens if the tree is empty?

The function returns 0 immediately (execution_sample code line 2), so no queue or width calculations happen.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the width calculated for level 2?

A 4

B 3

C 2

D 1

💡 Hint

Check the 'Width Calculation' column at step 7 in execution_table

At which step does maxWidth update from 2 to 4?

A Step 6

B Step 7

C Step 4

D Step 10

💡 Hint

Look at the 'Max Width' column in execution_table rows 4, 6, and 7

If the root had no children, what would be the maxWidth returned?

A 0

B 2

C 1

D Undefined

💡 Hint

Refer to variable_tracker and execution_sample code for empty children scenario

Concept Snapshot

Maximum Width of Binary Tree:
- Use level order traversal with a queue
- Track node indices to measure width
- Width = last index - first index + 1
- Normalize indices each level to avoid overflow
- Return max width found after all levels

Full Transcript

This concept finds the maximum width of a binary tree by traversing it level by level. We use a queue to hold nodes along with their position indices. At each level, we calculate the width by subtracting the first node's index from the last node's index and adding one. We update the maximum width if the current level's width is larger. We normalize indices at each level to keep numbers small. If the tree is empty, the width is zero. This method ensures we count null gaps between nodes correctly, giving the true maximum width.