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.

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 term 'width' in a tree

   The width of a binary tree at a level is the count of nodes present at that level.

2. Step 2: Define 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, find max count [OK]

Common Mistakes:

• Confusing width with tree height
• Counting total nodes instead of per level
• Summing node values instead of counting nodes

2. Which of the following C++ code snippets correctly declares a queue to store pairs of TreeNode pointers and their indices for width calculation?

easy

A. queue> q;

B. std::queue q;

C. std::queue> q;

D. std::queue> q;

Solution

1. Step 1: Understand queue declaration with pairs

   To store pairs, use std::pair with template parameters inside std::queue<>.

2. Step 2: Check syntax correctness

   std::queue> q; correctly uses std::queue> q; which is valid C++ syntax.

3. Final Answer:

   std::queue> q; -> Option D

4. Quick Check:

   Queue of pairs syntax = std::queue> [OK]

Hint: Use std::pair inside std::queue with angle brackets [OK]

Common Mistakes:

• Missing std::pair<> inside queue
• Incorrect template syntax
• Omitting std:: prefix

3. Given the following binary tree and code snippet, what is the maximum width printed?

struct TreeNode {
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// Tree structure:
//       1
//      / \
//     2   3
//    /     \
//   4       5

int maxWidth(TreeNode* root) {
  if (!root) return 0;
  std::queue> q;
  q.push({root, 0});
  int maxWidth = 0;
  while (!q.empty()) {
    int size = q.size();
    int start = q.front().second;
    int end = start;
    for (int i = 0; i < size; i++) {
      auto [node, idx] = q.front(); q.pop();
      end = idx;
      if (node->left) q.push({node->left, 2 * idx + 1});
      if (node->right) q.push({node->right, 2 * idx + 2});
    }
    maxWidth = std::max(maxWidth, end - start + 1);
  }
  return maxWidth;
}

// Call: maxWidth(root);

medium

A. 2

B. 3

C. 4

D. 5

Solution

1. Step 1: Analyze tree levels and node indices

   Level 0: Node 1 at index 0 (width = 1) Level 1: Nodes 2 (1), 3 (2) width = 2 Level 2: Nodes 4 (3), 5 (6) width = 6 - 3 + 1 = 4

2. Step 2: Calculate maximum width using code logic

   Code calculates width as end - start + 1 per level. Level 2 width is 4, which is maximum.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Max width = 4 nodes at level 2 [OK]

Hint: Track indices per level, width = end - start + 1 [OK]

Common Mistakes:

• Counting nodes without index gaps
• Ignoring index-based width calculation
• Assuming width equals node count only

4. Identify the bug in the following code snippet that attempts to compute the maximum width of a binary tree:

int widthOfBinaryTree(TreeNode* root) {
  std::queue> q;
  q.push({root, 0});
  int maxWidth = 0;
  while (!q.empty()) {
    int size = q.size();
    int start = q.front().second;
    int end = q.back().second;
    maxWidth = std::max(maxWidth, end - start + 1);
    for (int i = 0; i < size; i++) {
      auto [node, idx] = q.front(); q.pop();
      if (node->left) q.push({node->left, 2 * idx + 1});
      if (node->right) q.push({node->right, 2 * idx + 2});
    }
  }
  return maxWidth;
}

medium

A. Not checking if root is nullptr before processing

B. Using q.back().second before popping nodes causes incorrect width calculation

C. Incorrect indexing formula for child nodes

D. Missing return statement at the end

Solution

1. Step 1: Analyze the width calculation timing

   The code calculates width using q.back().second before popping nodes in the current level.

2. Step 2: Identify the bug

   Since q.back() includes nodes from the next level (pushed during previous iteration), width calculation is incorrect.

3. Final Answer:

   Using q.back().second before popping nodes causes incorrect width calculation -> Option B

4. Quick Check:

   Calculate width after popping all nodes at current level [OK]

Hint: Calculate width after processing current level nodes [OK]

Common Mistakes:

• Forgetting root null check
• Misplacing width calculation inside loop
• Wrong child index formulas

5. You want to find the maximum width of a binary tree that may have missing nodes between left and right children at some levels. Which approach correctly handles gaps caused by missing nodes?

hard

A. Use level order traversal with node indices to track positions and calculate width as end - start + 1

B. Count only the number of nodes at each level ignoring their positions

C. Calculate width as the difference between maximum and minimum node values at each level

D. Use depth-first traversal and count nodes recursively without indices

Solution

1. Step 1: Understand the problem with missing nodes

   Missing nodes create gaps, so counting nodes alone misses true width.

2. Step 2: Use indices to track node positions

   Assign indices to nodes as if in a full binary tree to capture gaps, then width = end - start + 1.

3. Final Answer:

   Use level order traversal with node indices to track positions and calculate width as end - start + 1 -> Option A

4. Quick Check:

   Index-based width handles gaps correctly [OK]

Hint: Track node indices to include gaps in width calculation [OK]

Common Mistakes:

• Ignoring gaps by counting nodes only
• Using node values instead of positions
• Using DFS without position tracking