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.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The largest number of nodes present at any single level of the tree

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The sum of values of all nodes at the widest level

Solution

1. Step 1: Understand the definition of width in a binary tree

   The width is the count of nodes at a particular level in the tree.

2. Step 2: Identify maximum width

   The maximum width is the largest such count among all levels.

3. Final Answer:

   The largest number of nodes present at any single level of the tree -> Option A

4. Quick Check:

   Maximum width = max nodes at any level [OK]

Hint: Width means count of nodes at one level, not height or sum [OK]

Common Mistakes:

• Confusing width with height of the tree
• Thinking width is total nodes in the tree
• Assuming width is sum of node values

2. Which TypeScript data structure is best suited to track nodes level by level when finding maximum width of a binary tree?

easy

A. Queue

B. Stack

C. Set

D. Map

Solution

1. Step 1: Identify traversal method for levels

   Level order traversal visits nodes level by level, which uses a queue.

2. Step 2: Choose data structure for level order

   A queue allows FIFO order, perfect for processing nodes in each level sequentially.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level-by-level traversal [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Using set which doesn't maintain order
• Using map which is key-value, not for traversal order

3. What will be the output of the following TypeScript code snippet that calculates maximum width of a binary tree?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.right = new TreeNode(5);

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

console.log(maxWidth(root));

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze tree structure and levels

   Level 1: Node 1 (width 1) Level 2: Nodes 2, 3 (width 2) Level 3: Nodes 4, 5 (width 2)

2. Step 2: Check code logic for max width

   Code tracks queue length per level and updates maxWidth. Max width found is 2 at levels 2 and 3.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at widest level [OK]

Hint: Count nodes per level, track max count [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Assuming width is height of tree
• Ignoring null children in width calculation

4. The following TypeScript function aims to find the maximum width of a binary tree but has a bug. What is the bug?

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i <= levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

medium

A. The maxWidth should be updated after the for loop

B. The queue should be a stack for correct traversal

C. The for loop condition should be i < levelSize, not i <= levelSize

D. The function should return queue.length instead of maxWidth

Solution

1. Step 1: Examine the for loop condition

   The loop runs from i = 0 to i <= levelSize, which means it runs levelSize + 1 times.

2. Step 2: Identify impact of off-by-one error

   Calling queue.shift() one extra time causes undefined or error because queue is empty after levelSize removals.

3. Final Answer:

   The for loop condition should be i < levelSize, not i <= levelSize -> Option C

4. Quick Check:

   Loop runs exactly levelSize times [OK]

Hint: Use i < levelSize for loops over fixed-size levels [OK]

Common Mistakes:

• Using <= instead of < in loops causing extra iteration
• Confusing queue with stack for level order
• Updating maxWidth inside loop incorrectly

5. Given a binary tree where some nodes are missing (null), how can you modify the maximum width calculation to include the 'null' positions between nodes, so the width counts the distance between the leftmost and rightmost non-null nodes at each level? Choose the best approach to solve this problem in TypeScript.

hard

A. Count only non-null nodes per level ignoring positions

B. Calculate width by summing values of nodes at each level

C. Use a stack instead of a queue to track nodes

D. Assign an index to each node as if the tree was a complete binary tree, then calculate width as rightmost index - leftmost index + 1 per level

Solution

1. Step 1: Understand the problem with missing nodes

   Simply counting nodes misses gaps caused by nulls, so width must consider positions.

2. Step 2: Use indexing like a complete binary tree

   Assign indices to nodes: root = 0, left child = 2*index, right child = 2*index + 1. Track min and max indices per level to find width including gaps.

3. Final Answer:

   Assign an index to each node as if the tree was a complete binary tree, then calculate width as rightmost index - leftmost index + 1 per level -> Option D

4. Quick Check:

   Index nodes to include null gaps [OK]

Hint: Use complete tree indexing to count gaps [OK]

Common Mistakes:

• Ignoring null gaps and counting only nodes
• Using stack which breaks level order
• Summing node values instead of counting width