Maximum Width of Binary Tree in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare a queue node pointer for BFS traversal.

DSA C

struct QueueNode* [1] = NULL;

Drag options to blanks, or click blank then click option'

Afront

Broot

Ctemp

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'root' as queue pointer instead of 'front'.

Using a temporary variable name that does not represent queue front.

The queue front pointer is commonly named 'front' to track the start of the queue.

2fill in blank

medium

Complete the code to enqueue a binary tree node into the queue.

DSA C

enqueue(queue, [1]);

Drag options to blanks, or click blank then click option'

Anode

BNULL

Cnode->right

Dnode->left

Attempts:

3 left

💡 Hint

Common Mistakes

Enqueuing NULL instead of a valid node.

Enqueuing children before the current node.

We enqueue the current node itself to start BFS traversal.

3fill in blank

hard

Fix the error in the condition to check if the queue is empty.

DSA C

while ([1] != NULL) {

Drag options to blanks, or click blank then click option'

Aroot

Brear

Cfront

Dtemp

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'rear' instead of 'front' for emptiness.

Checking 'root' which is unrelated to queue state.

The queue is empty when 'front' is NULL, so we loop while 'front' is not NULL.

4fill in blank

hard

Fill both blanks to calculate the width of the current level.

DSA C

int width = [1] - [2] + 1;

Drag options to blanks, or click blank then click option'

ArightIndex

BleftIndex

Clevel

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using level or count instead of node indices.

Subtracting leftIndex from rightIndex without adding 1.

Width is calculated as rightmost index minus leftmost index plus one.

5fill in blank

hard

Fill all three blanks to assign indices to child nodes during BFS.

DSA C

if (node->left) { enqueue(queue, node->left); node->left->index = [1] * 2 + [2]; }
if (node->right) { enqueue(queue, node->right); node->right->index = [3] * 2 + 1; }

Drag options to blanks, or click blank then click option'

Anode->index

B0

C1

Dlevel

Attempts:

3 left

💡 Hint

Common Mistakes

Using level instead of parent's index.

Using +1 for left child index instead of +0.

Left child's index = parent's index * 2 + 0; right child's index = parent's index * 2 + 1.

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