Maximum Width of Binary Tree in DSA Javascript - 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 until all levels processed

↓

Return max width found

We start from the root and use a queue to traverse level by level, tracking node positions to find the maximum width.

Execution Sample

DSA Javascript

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

This code finds the maximum width of a binary tree by tracking node indices level-wise.

Execution Table

Step	Operation	Nodes in Queue	Pointer Changes	Visual State
1	Initialize queue with root (index 0)	[[1,0]]	queue = [[1,0]]	Level 0: 1(0)
2	Process level 0: pop node 1 at index 0	[]	queue.shift() -> [1,0]	Level 0 processed
3	Add children of node 1: left=2 at index 1, right=3 at index 2	[[2,1],[3,2]]	queue.push([2,1]), queue.push([3,2])	Level 1: 2(1) -> 3(2)
4	Calculate width level 0: lastIndex 0 - firstIndex 0 + 1 = 1	[[2,1],[3,2]]	maxWidth = 1	Max width updated to 1
5	Process level 1: pop node 2 at index 1	[[3,2]]	queue.shift() -> [2,1]	Processing node 2
6	Add children of node 2: left=4 at index 3, right=5 at index 4	[[3,2],[4,3],[5,4]]	queue.push([4,3]), queue.push([5,4])	Level 2: 4(3) -> 5(4)
7	Process level 1: pop node 3 at index 2	[[4,3],[5,4]]	queue.shift() -> [3,2]	Processing node 3
8	Add children of node 3: none	[[4,3],[5,4]]	No children added	Level 2 unchanged
9	Calculate width level 1: lastIndex 2 - firstIndex 1 + 1 = 2	[[4,3],[5,4]]	maxWidth = 2	Max width updated to 2
10	Process level 2: pop node 4 at index 3	[[5,4]]	queue.shift() -> [4,3]	Processing node 4
11	Add children of node 4: none	[[5,4]]	No children added	Level 3 unchanged
12	Process level 2: pop node 5 at index 4	[]	queue.shift() -> [5,4]	Processing node 5
13	Add children of node 5: none	[]	No children added	Level 3 empty
14	Calculate width level 2: lastIndex 4 - firstIndex 3 + 1 = 2	[]	maxWidth = 2	Max width remains 2
15	Queue empty, end loop	[]	Return maxWidth = 2	Final max width = 2

💡 Queue is empty, all levels processed, maximum width found is 2

Variable Tracker

Variable	Start	After Step 3	After Step 6	After Step 9	After Step 14	Final
queue	[[1,0]]	[[2,1],[3,2]]	[[3,2],[4,3],[5,4]]	[[4,3],[5,4]]	[]	[]
maxWidth	0	1	1	2	2	2
firstIndex	0	1	1	1	-	-
lastIndex	0	2	4	4	-	-

Key Moments - 3 Insights

Why do we assign indices to nodes in the queue?

Indices help us calculate the width by showing the position of nodes in the level. See steps 3, 6, and 9 where indices are used to find width.

Why do we subtract firstIndex from lastIndex and add 1 to get width?

Because width counts all positions between first and last nodes inclusive. This is shown in steps 4, 9, and 14 in the execution table.

Why do we multiply index by 2 and add 1 or 2 for children?

This simulates the position of left and right children in a full binary tree, keeping track of gaps. See steps 3 and 6 for how children indices are calculated.

Visual Quiz - 3 Questions

Look at the execution table at step 9, what is the maxWidth value?

A 1

B 2

C 3

D 4

💡 Hint

Check the 'maxWidth' column in the execution table row for step 9.

At which step does the queue become empty, ending the loop?

A Step 14

B Step 13

C Step 15

D Step 10

💡 Hint

Look at the 'Queue' column in the execution table to find when it is empty.

If the root had no children, what would be the maximum width?

A 1

B 2

C 0

D Undefined

💡 Hint

Refer to the initial queue state and width calculation at step 4.

Concept Snapshot

Maximum Width of Binary Tree:
- Use level order traversal with a queue
- Assign indices to nodes to track positions
- Width = last index - first index + 1 per level
- Update max width after each level
- Return max width after processing all levels

Full Transcript

To find the maximum width of a binary tree, we start at the root and use a queue to traverse level by level. Each node is paired with an index representing its position if the tree was complete. For 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 add children to the queue with calculated indices and repeat until all levels are processed. Finally, we return the maximum width found.