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 current width is larger

↓

Add children to queue with updated indices

↓

Repeat for next level

↓

Return max width

We start from the root, use a queue to traverse level by level, track node positions to find width, and update max width until all levels are processed.

Execution Sample

DSA C

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

This code calculates the maximum width of a binary tree by level order traversal using a queue and tracking indices.

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	[1:0]	Pop (1,0), push left (2,1), push right (3,2)	Level 0 processed, width=1
3	Queue after level 0	[2:1, 3:2]	Queue updated	Level 1: [2:1, 3:2]
4	Process level 1	[2:1, 3:2]	Pop (2,1), push left (4,3), pop (3,2), push right (5,6)	Level 1 processed, width=2
5	Queue after level 1	[4:3, 5:6]	Queue updated	Level 2: [4:3, 5:6]
6	Process level 2	[4:3, 5:6]	Pop (4,3), no children, pop (5,6), no children	Level 2 processed, width=4
7	Queue after level 2	[]	Queue empty	Traversal complete
8	Return max width	-	-	Max width = 4

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

Variable Tracker

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

Key Moments - 3 Insights

Why do we subtract 'start' from node indices inside the loop?

Subtracting 'start' normalizes indices to prevent overflow and keeps indices small for each level, as shown in execution_table rows 4 and 6.

Why do we calculate width as 'end - start + 1'?

Because indices represent positions, width is the distance between first and last node indices plus one, as seen in execution_table rows 2, 4, and 6.

What happens if the tree is empty?

The function returns 0 immediately (execution_sample line 2), no queue operations happen.

Visual Quiz - 3 Questions

Look at the execution_table at Step 4, what is the width calculated for level 1?

A 1

B 3

C 2

D 4

💡 Hint

Check the 'Visual State' column at Step 4 showing width=2

At which step does the queue become empty?

A Step 6

B Step 7

C Step 5

D Step 8

💡 Hint

Look at the 'Nodes in Queue' column; empty queue is at Step 7

If the root had only one child on the left, how would maxWidth change after Step 2?

A maxWidth would be 1

B maxWidth would be 2

C maxWidth would be 0

D maxWidth would be 3

💡 Hint

Refer to variable_tracker 'maxWidth' after Step 2 and consider only one child added

Concept Snapshot

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

Full Transcript

To find the maximum width of a binary tree, we start from the root node and 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 as last minus first plus one. We update the maximum width if the current level's width is larger. We add children nodes to the queue with updated indices to maintain position tracking. This continues until all levels are processed and the queue is empty. The final maximum width is returned. This method handles empty trees by returning zero immediately.

Practice

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

easy

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

B. The number of leaf nodes in the tree

C. The total number of nodes in the tree

D. The largest value of (lastIndex - firstIndex + 1) at any single level of the tree

Solution

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

   The width of a level is defined as (rightmost node index - leftmost node index + 1), where children indices are 2*parent and 2*parent+1. Maximum width is the maximum over all levels.

2. Step 2: Compare with other tree properties

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

3. Final Answer:

   The largest value of (lastIndex - firstIndex + 1) at any single level of the tree -> Option D

4. Quick Check:

   Width = max(lastIndex - firstIndex + 1) [OK]

Hint: Width means max (last - first +1) at one level using indices, not height or total nodes [OK]

Common Mistakes:

• Confusing width with height
• Thinking width is total nodes
• Thinking width is just count of nodes ignoring gaps
• Mixing width with leaf count

2. Which of the following C code snippets correctly declares a queue node structure for level order traversal in maximum width calculation?

easy

A. typedef struct QueueNode { struct TreeNode* node; unsigned int index; struct QueueNode* next; } QueueNode;

B. struct QueueNode { int value; struct QueueNode* prev; };

C. typedef struct QueueNode { struct TreeNode* node; int level; } QueueNode;

D. struct QueueNode { struct TreeNode* node; struct QueueNode* next; int data; };

Solution

1. Step 1: Identify required fields for maximum width queue node

   We need a pointer to tree node, an index for position, and next pointer for queue linking.

2. Step 2: Check each option for these fields

   typedef struct QueueNode { struct TreeNode* node; unsigned int index; struct QueueNode* next; } QueueNode; has node pointer, index, and next pointer correctly typed.

3. Final Answer:

   typedef struct QueueNode { struct TreeNode* node; unsigned int index; struct QueueNode* next; } QueueNode; -> Option A

4. Quick Check:

   Queue node needs node, index, next [OK]

Hint: Queue node must store tree node pointer and index for width [OK]

Common Mistakes:

• Missing index field for position tracking
• Using wrong pointer types
• Confusing prev and next pointers

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

    1
   / \
  2   3
 /     \
4       5

// Code snippet:
int maxWidth = maximumWidth(root);
printf("%d", maxWidth);

medium

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Analyze the tree levels and node indices

   Assume root index 0.
   Level 0: 1 (idx 0), width=1
   Level 1: 2 (idx 0), 3 (idx 1), width=2
   Level 2: 4 (idx 0, left of 2), 5 (idx 3, right of 3), width=4

2. Step 2: Determine maximum width

   Maximum span (last - first +1) is 4 at level 2.

3. Final Answer:

   4 -> Option C

4. Quick Check:

   Max width = 4 at level 2 [OK]

Hint: Trace BFS with indices: level spans 1,2,4 -> max 4 [OK]

Common Mistakes:

• Counting only nodes per level (gets 2)
• Wrong child index calculation
• Misreading tree connections
• Forgetting gaps in span

4. Identify the bug in this C code snippet for calculating maximum width of a binary tree:

unsigned int maximumWidth(struct TreeNode* root) {
    if (!root) return 0;
    unsigned int maxWidth = 0;
    QueueNode* queue = createQueue();
    enqueue(queue, root, 0);
    while (!isEmpty(queue)) {
        unsigned int size = queueSize(queue);
        unsigned int firstIndex = queueFrontIndex(queue);
        unsigned int lastIndex = queueBackIndex(queue);
        maxWidth = max(maxWidth, lastIndex - firstIndex + 1);
        for (unsigned int i = 0; i < size; i++) {
            QueueNode* curr = dequeue(queue);
            if (curr->node->left) enqueue(queue, curr->node->left, 2 * curr->index);
            if (curr->node->right) enqueue(queue, curr->node->right, 2 * curr->index + 1);
        }
    }
    return maxWidth;
}

medium

A. The loop uses 'i < size' but size changes inside the loop

B. The max function is not defined or included

C. The index calculation for children should add 1 to avoid overlap

D. Indexing starts at 0, should start at 1 to avoid zero-based errors

Solution

1. Step 1: Check for missing function definitions

   The code uses max() but does not define or include it, causing compile error.

2. Step 2: Verify other parts for correctness

   Indexing from 0 is valid, size is fixed per loop iteration, child index calculation 2*i and 2*i+1 is correct for span.

3. Final Answer:

   The max function is not defined or included -> Option B

4. Quick Check:

   Undefined max() causes error [OK]

Hint: Check if all functions like max() are defined or included [OK]

Common Mistakes:

• Assuming max() is built-in in C
• Thinking indexing must start at 1
• Believing queue size changes inside loop

5. You have a binary tree where some levels have missing nodes between existing nodes. How should you calculate the maximum width to include these gaps correctly?

hard

A. Use node indices based on complete binary tree positions to measure width including gaps

B. Count only existing nodes at each level ignoring gaps

C. Calculate width as the difference between max and min node values at each level

D. Use height of the tree multiplied by 2 as width

Solution

1. Step 1: Understand the problem of gaps in levels

   Missing nodes create gaps; counting nodes alone underestimates true width.

2. Step 2: Use indexing to capture gaps

   Assign indices as if tree is complete (left: 2*parent, right: 2*parent+1); width = last index - first index + 1 captures gaps.

3. Final Answer:

   Use node indices based on complete binary tree positions to measure width including gaps -> Option A

4. Quick Check:

   Indexing captures gaps for true width [OK]

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

Common Mistakes:

• Ignoring gaps and counting only nodes
• Using node values instead of positions
• Confusing width with height