Maximum Width of Binary Tree in DSA Java - 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 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 Java

class Solution {
  public int widthOfBinaryTree(TreeNode root) {
    // BFS with index tracking
  }
}

This code finds the maximum width of a binary tree using breadth-first search and indexing nodes.

Execution Table

Step	Operation	Nodes in Queue (node:index)	First Index	Last Index	Width	Max Width	Visual Tree State
1	Initialize queue with root (1:0)	[1:0]	0	0	1	1	1
2	Process level 1	[1:0]	0	0	1	1	1
3	Add children (2:0, 3:1)	[2:0, 3:1]	0	1	2	2	1 / \ 2 3
4	Process level 2	[2:0, 3:1]	0	1	2	2	1 / \ 2 3
5	Add children (5:0, 9:3)	[5:0, 9:3]	0	3	4	4	1 / \ 2 3 / \ 5 9
6	Process level 3	[5:0, 9:3]	0	3	4	4	1 / \ 2 3 / \ 5 9
7	Add children (6:1, 7:2)	[6:1, 7:2]	1	2	2	4	1 / \ 2 3 / \ 5 9 \ / 6 7
8	Process level 4	[6:1, 7:2]	1	2	2	4	1 / \ 2 3 / \ 5 9 \ / 6 7
9	No more children to add	[]	-	-	-	4	1 / \ 2 3 / \ 5 9 \ / 6 7
10	End traversal	[]	-	-	-	4	Max width found is 4

💡 Queue empty means all levels processed; max width is 4

Variable Tracker

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

Key Moments - 3 Insights

Why do we assign indices to nodes during BFS?

Indices represent the node's position as if the tree was a full binary tree, allowing calculation of width even with missing nodes. See execution_table steps 3, 5, and 7 where indices help find width.

Why is width calculated as last index - first index + 1?

Because indices start at 0, the width includes both ends, so we add 1. This is shown in execution_table width column at steps 3, 5, and 7.

Why does the queue hold pairs of (node, index)?

To track each node's position in the level for width calculation. Without indices, we can't measure gaps caused by missing nodes. See variable_tracker queue changes.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the width calculated for that level?

A 3

B 4

C 2

D 5

💡 Hint

Check the Width column at step 5 in execution_table

At which step does the maxWidth first update to 4?

A Step 5

B Step 3

C Step 7

D Step 9

💡 Hint

Look at the Max Width column in execution_table and find when it changes to 4

If the tree had no right child at level 3, how would the queue change after step 5?

A Queue would be empty

B Queue would have nodes with indices 0 and 1

C Queue would have only one node with index 0

D Queue would have nodes with indices 1 and 2

💡 Hint

Refer to variable_tracker queue state and how children are added with indices

Concept Snapshot

Maximum Width of Binary Tree:
- Use BFS level order traversal
- Assign indices to nodes as if full binary tree
- Width = last index - first index + 1 per level
- Track max width across levels
- Return max width after traversal

Full Transcript

This concept finds the maximum width of a binary tree by traversing it level by level using a queue. Each node is paired with an index representing its position in a full binary tree. At each level, the width is calculated by subtracting the first node's index from the last node's index and adding one. The maximum width is updated if the current level's width is larger. The process continues until all levels are processed, and the maximum width found 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 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, find max [OK]

Common Mistakes:

• Confusing width with tree height
• Thinking width is sum of node values
• Counting total nodes instead of per level

2. Which Java data structure is most suitable to track nodes level by level when finding maximum width of a binary tree?

easy

A. Stack

B. HashMap

C. Queue

D. ArrayList

Solution

1. Step 1: Identify traversal method for level order

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

2. Step 2: Choose data structure

   A queue allows nodes to be added and removed in FIFO order, perfect for level traversal.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Level order traversal uses queue [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 HashMap which doesn't preserve order
• Using ArrayList without queue behavior

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

class TreeNode {
  int val;
  TreeNode left, right;
  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);

// Maximum width calculation
int maxWidth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}
System.out.println(maxWidth);

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze tree levels and node counts

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

2. Step 2: Determine maximum width

   The maximum number of nodes at any level is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at level 2 [OK]

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

Common Mistakes:

• Counting total nodes instead of per level
• Assuming level 3 has 3 nodes incorrectly
• Ignoring null children in width calculation

4. Identify the bug in this Java code snippet that attempts to find the maximum width of a binary tree:

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int maxWidth = 0;
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i <= size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}

medium

A. The loop condition should be i < size, not i <= size

B. The queue should be a Stack instead

C. maxWidth should be updated after the for loop

D. The root node is never added to the queue

Solution

1. Step 1: Check the for loop iteration count

   The loop runs from i = 0 to i <= size, which means it runs size+1 times, causing an extra poll.

2. Step 2: Correct the loop condition

   It should run exactly size times, so condition must be i < size.

3. Final Answer:

   The loop condition should be i < size, not i <= size -> Option A

4. Quick Check:

   Loop must run size times exactly [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using <= instead of < in for loop
• Replacing queue with stack incorrectly
• Updating maxWidth at wrong place

5. Given a binary tree where some nodes are missing children, how can you modify the maximum width calculation to include 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.

hard

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

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

C. Use a stack to store nodes and count them

D. Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1

Solution

1. Step 1: Understand the problem with missing nodes

   Simple counting misses gaps caused by null children, so width is underestimated.

2. Step 2: Use indexing to simulate complete tree positions

   Assign indices to nodes as in a complete binary tree (root=0, left=2*index, right=2*index+1).

3. Step 3: Calculate width per level using min and max indices

   Width = max index - min index + 1, capturing gaps between nodes.

4. Final Answer:

   Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1 -> Option D

5. Quick Check:

   Indexing nodes captures gaps for accurate width [OK]

Hint: Use node indices to count gaps for true width [OK]

Common Mistakes:

• Ignoring null gaps between nodes
• Counting only non-null nodes without positions
• Using stack instead of queue for level traversal