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 first and last index

↓

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 start from the root, use a queue to track nodes level by level with indices, calculate width per level, and update max width.

Execution Sample

DSA C#

int MaxWidth(TreeNode root) {
  if (root == null) return 0;
  Queue<(TreeNode node, int index)> q = new();
  q.Enqueue((root, 0));
  int maxWidth = 0;
  while (q.Count > 0) {
    int count = q.Count;
    int start = q.Peek().index;
    int end = start;
    for (int i = 0; i < count; i++) {
      var (node, idx) = q.Dequeue();
      end = idx;
      if (node.left != null) q.Enqueue((node.left, 2 * idx + 1));
      if (node.right != null) q.Enqueue((node.right, 2 * idx + 2));
    }
    maxWidth = Math.Max(maxWidth, end - start + 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 (node:value,index)	Pointer Changes	Visual Tree State
1	Initialize queue with root (1,0)	[(1,0)]	Enqueue root with index 0	1(0)
2	Process level 1	[(1,0)]	Dequeue (1,0), enqueue (2,1), (3,2)	1(0) ├─2(1) └─3(2)
3	Process level 2	[(2,1),(3,2)]	Dequeue (2,1), enqueue (4,3), (5,4) Dequeue (3,2), enqueue (7,6)	1(0) ├─2(1) │ ├─4(3) │ └─5(4) └─3(2) └─7(6)
4	Process level 3	[(4,3),(5,4),(7,6)]	Dequeue (4,3), no children Dequeue (5,4), no children Dequeue (7,6), no children	1(0) ├─2(1) │ ├─4(3) │ └─5(4) └─3(2) └─7(6)
5	Queue empty, end	[]	No nodes left	Final tree unchanged

💡 Queue is empty, all levels processed, max width found

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
maxWidth	0	3	5	5	5
queue count	1	2	3	0	0
start index	-	0	1	3	-
end index	-	0	2	6	-

Key Moments - 3 Insights

Why do we assign indices like 2*idx+1 and 2*idx+2 to children?

This indexing simulates positions in a full binary tree, helping calculate width by comparing first and last indices at each level (see execution_table rows 2 and 3).

Why do we subtract start index from end index and add 1 for width?

Because indices start from zero, width is the count of positions between first and last nodes inclusive (see execution_table row 4 where width = 6 - 3 + 1 = 4).

What happens if the tree is empty?

The function returns 0 immediately as shown in the code sample, no queue operations happen.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the maxWidth after processing this level?

A 1

B 2

C 3

D 4

💡 Hint

Check the maxWidth value in variable_tracker after Step 3

At which step does the queue become empty?

A Step 5

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the queue count column in variable_tracker and execution_table rows

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

A 0

B 1

C 2

D Undefined

💡 Hint

Refer to the initial queue state and maxWidth updates in execution_table Step 1

Concept Snapshot

Maximum Width of Binary Tree:
- Use BFS with queue storing (node, index)
- Index children as 2*idx+1 (left), 2*idx+2 (right)
- Width per level = last_index - first_index + 1
- Track max width across levels
- Return max width after traversal

Full Transcript

This visualization shows how to find the maximum width of a binary tree. We start at the root node with index 0 and use a queue to process nodes level by level. Each node is paired with an index representing its position in a full binary tree. For each level, we note the first and last indices to calculate the width as last minus first plus one. We update the maximum width found so far. Children nodes are added to the queue with calculated indices. This continues until all levels are processed and the queue is empty. The final maximum width is returned. The execution table tracks queue contents, pointer changes, and visual tree state at each step. Variable tracker shows how maxWidth and queue size change. Key moments clarify indexing and width calculation. The quiz tests understanding of maxWidth values and queue emptiness timing.

Practice

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

easy

A. The number of leaf nodes in 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 largest number of nodes present at any single level of the tree

Solution

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

   The width is the count of nodes at the widest level of the tree.

2. Step 2: Compare with other tree properties

   Height is depth, total nodes is size, leaves are end nodes, none represent width.

3. Final Answer:

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

4. Quick Check:

   Width = max nodes at one level [OK]

Hint: Width means max nodes at one level, not height or total nodes [OK]

Common Mistakes:

• Confusing width with height
• Thinking width is total nodes
• Mixing width with leaf count

2. Which C# data structure is best suited to help calculate the maximum width of a binary tree level by level?

easy

A. Queue

B. Stack

C. Dictionary

D. List

Solution

1. Step 1: Identify traversal method for level-wise processing

   Level order traversal uses a queue to process nodes level by level.

2. Step 2: Match data structure to traversal

   Queue supports FIFO, perfect for breadth-first search to measure width.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Queue = level order traversal tool [OK]

Hint: Use queue for level order traversal to measure width [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Choosing dictionary which stores key-value pairs, not order
• Using list without queue behavior

3. What is the output of the following C# code snippet that calculates the maximum width of a binary tree?

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int v) { val = v; }
}

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

TreeNode 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);

int MaxWidth(TreeNode root) {
    if (root == null) return 0;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int maxWidth = 0;
    while (queue.Count > 0) {
        int count = queue.Count;
        maxWidth = Math.Max(maxWidth, count);
        for (int i = 0; i < count; i++) {
            var node = queue.Dequeue();
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return maxWidth;
}

Console.WriteLine(MaxWidth(root));

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Analyze tree levels and node counts

   Level 1: 1 node (1), Level 2: 2 nodes (2,3), Level 3: 2 nodes (4,5).

2. Step 2: Determine maximum width from levels

   Maximum width is 2 at levels 2 and 3.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Max width = 2 nodes at widest level [OK]

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

Common Mistakes:

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

4. Identify the bug in this C# method that attempts to find the maximum width of a binary tree:

int MaxWidth(TreeNode root) {
    if (root == null) return 0;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int maxWidth = 0;
    while (queue.Count > 0) {
        int count = queue.Count;
        maxWidth = Math.Max(maxWidth, count);
        for (int i = 0; i <= count; i++) {
            var node = queue.Dequeue();
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return maxWidth;
}

medium

A. The maxWidth should be updated after the for loop

B. The for loop condition should be i < count, not i <= count

C. The queue should be a stack for correct traversal

D. The method should return count instead of maxWidth

Solution

1. Step 1: Check for off-by-one error in loop

   The for loop runs from i = 0 to i <= count, which runs count+1 times causing dequeue error.

2. Step 2: Correct loop condition

   Change to i < count to run exactly count times matching queue size at start of loop.

3. Final Answer:

   The for loop condition should be i < count, not i <= count -> Option B

4. Quick Check:

   Loop runs count times, not count+1 [OK]

Hint: For loops over queue size use i < count, not i <= count [OK]

Common Mistakes:

• Using <= instead of < causing runtime errors
• Replacing queue with stack breaking level order
• Updating maxWidth at wrong time

5. Given a binary tree where some nodes are missing (null), how can you modify the maximum width calculation to count the width including null positions between nodes? Example tree: // 1 // / \ // 2 3 // \ \ // 4 5 What approach correctly calculates the maximum width as 3 for this tree?

hard

A. Assign position indices to nodes and calculate width as max index difference + 1 per level

B. Count only non-null nodes at each level ignoring gaps

C. Use depth-first traversal and count leaf nodes

D. Calculate width as total nodes minus null nodes

Solution

1. Step 1: Understand the problem with null gaps

   Simple counting ignores null gaps, so width underestimates actual spread.

2. Step 2: Use position indices to track node positions

   Assign indices like a heap: root=0, left=2*index+1, right=2*index+2, then width = max index - min index + 1 per level.

3. Step 3: Calculate width using indices

   This method counts null gaps, giving correct width of 3 in example.

4. Final Answer:

   Assign position indices to nodes and calculate width as max index difference + 1 per level -> Option A

5. Quick Check:

   Indexing nodes counts gaps, width = max-min+1 [OK]

Hint: Use node indices to include null gaps in width [OK]

Common Mistakes:

• Ignoring null gaps between nodes
• Counting only existing nodes per level
• Using DFS instead of BFS for width