Maximum Width of Binary Tree in DSA C++ - 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 size

↓

Record first and last node indices

↓

Calculate width = last - first + 1

↓

Update max width if larger

↓

Add children to queue with updated indices

↓

Repeat for next level

↓

Return max width

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

Execution Sample

DSA C++

int widthOfBinaryTree(TreeNode* root) {
  if (!root) return 0;
  unsigned long long maxWidth = 0;
  queue<pair<TreeNode*, unsigned long long>> q;
  q.push({root, 0});
  while (!q.empty()) {
    int size = q.size();
    unsigned long long start = q.front().second;
    unsigned long long end = q.back().second;
    maxWidth = max(maxWidth, end - start + 1);
    for (int i = 0; i < size; i++) {
      auto [node, idx] = q.front(); q.pop();
      idx -= start;
      if (node->left) q.push({node->left, 2 * idx + 1});
      if (node->right) q.push({node->right, 2 * idx + 2});
    }
  }
  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: index)	Pointer Changes	Visual State
1	Initialize queue with root (1) at index 0	[1:0]	queue.push({1,0})	Level 0: [1:0]
2	Process level 0, size=1	[1:0]	start=0, end=0, maxWidth=1	Width=1 (0-0+1)
3	Pop node 1 at idx 0	[]	idx=0	Remove 1:0
4	Push left child 3 at idx 1	[3:1]	queue.push({3,1})	Level 1: [3:1]
5	Push right child 2 at idx 2	[3:1, 2:2]	queue.push({2,2})	Level 1: [3:1, 2:2]
6	Process level 1, size=2	[3:1, 2:2]	start=1, end=2, maxWidth=2	Width=2 (2-1+1)
7	Pop node 3 at idx 1	[2:2]	idx=0	Remove 3:1
8	Push left child 5 at idx 1	[2:2, 5:1]	queue.push({5,1})	Level 2: [2:2, 5:1]
9	Push right child 3 at idx 2	[2:2, 5:1, 3:2]	queue.push({3,2})	Level 2: [2:2, 5:1, 3:2]
10	Pop node 2 at idx 2	[5:1, 3:2]	idx=1	Remove 2:2
11	Push right child 9 at idx 4	[5:1, 3:2, 9:4]	queue.push({9,4})	Level 2: [5:1, 3:2, 9:4]
12	Process level 2, size=3	[5:1, 3:2, 9:4]	start=1, end=4, maxWidth=4	Width=4 (4-1+1)
13	Pop node 5 at idx 1	[3:2, 9:4]	idx=0	Remove 5:1
14	Pop node 3 at idx 2	[9:4]	idx=1	Remove 3:2
15	Pop node 9 at idx 4	[]	idx=3	Remove 9:4
16	Queue empty, return maxWidth=4	[]	End	Final max width = 4

💡 Queue is empty, all levels processed, maxWidth found

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 12	Final
maxWidth	0	1	2	4	4
queue	[(1,0)]	[(3,1),(2,2)]	[(5,1),(3,2),(9,4)]	[]	[]
start	-	0	1	1	-
end	-	0	2	4	-

Key Moments - 3 Insights

Why do we subtract 'start' from each index inside the loop?

Subtracting 'start' normalizes indices to prevent overflow and keeps indices small, as shown in steps 3, 7, 10, 13, 14, 15 in the execution_table.

Why do we use unsigned long long for indices?

Indices can grow large in deep trees; unsigned long long prevents overflow, ensuring correct width calculation as seen in variable_tracker for 'start' and 'end'.

How does the queue represent the current level nodes?

The queue holds pairs of nodes and their indices for the current level; after processing a level, children are added for the next level, visible in the 'Nodes in Queue' column.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the maxWidth value?

A 3

B 1

C 2

D 4

💡 Hint

Check the 'maxWidth' update in the 'Pointer Changes' column at step 6.

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

A Step 16

B Step 14

C Step 12

D Step 10

💡 Hint

Look for the step where 'Queue empty, return maxWidth=4' is noted in the 'Operation' column.

If the root had no children, what would be the maxWidth after step 2?

A 0

B 1

C 2

D Undefined

💡 Hint

Refer to step 2 where maxWidth is set after processing the root level.

Concept Snapshot

Maximum Width of Binary Tree:
- Use level order traversal with a queue
- Track node indices to calculate width
- Width = last index - first index + 1 per level
- Update max width after each level
- Return max width after traversal

Full Transcript

To find the maximum width of a binary tree, we use a queue to traverse the tree level by level. Each node is paired with an index representing its position. For each level, we record the first and last node indices to calculate the width. We update the maximum width if the current level's width is larger. We normalize indices by subtracting the first index of the level to avoid large numbers. This process continues until all levels are processed, and the maximum width is returned.