Maximum Width of Binary Tree in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation

What is the output of the following code that calculates the maximum width of a binary tree?

DSA C

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

// Queue node for BFS
typedef struct QueueNode {
    struct TreeNode* node;
    unsigned long long index;
    struct QueueNode* next;
} QueueNode;

// Queue structure
typedef struct Queue {
    QueueNode* front;
    QueueNode* rear;
} Queue;

void enqueue(Queue* q, TreeNode* node, unsigned long long index) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->index = index;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

void dequeue(Queue* q) {
    if (q->front == NULL) return;
    QueueNode* temp = q->front;
    q->front = q->front->next;
    if (q->front == NULL) q->rear = NULL;
    free(temp);
}

int isEmpty(Queue* q) {
    return q->front == NULL;
}

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    Queue q = {NULL, NULL};
    enqueue(&q, root, 0ULL);

    while (!isEmpty(&q)) {
        int size = 0;
        QueueNode* temp = q.front;
        while (temp) {
            size++;
            temp = temp->next;
        }

        unsigned long long start = q.front->index;
        unsigned long long end = q.rear->index;
        if (end - start + 1 > maxWidth) maxWidth = end - start + 1;

        for (int i = 0; i < size; i++) {
            TreeNode* node = q.front->node;
            unsigned long long idx = q.front->index;
            dequeue(&q);
            if (node->left) enqueue(&q, node->left, 2 * (idx - start));
            if (node->right) enqueue(&q, node->right, 2 * (idx - start) + 1);
        }
    }
    return (int)maxWidth;
}

int main() {
    TreeNode n1 = {1, NULL, NULL};
    TreeNode n2 = {3, NULL, NULL};
    TreeNode n3 = {2, NULL, NULL};
    TreeNode n4 = {5, NULL, NULL};
    TreeNode n5 = {3, NULL, NULL};
    TreeNode n6 = {9, NULL, NULL};

    n1.left = &n2;
    n1.right = &n3;
    n2.left = &n4;
    n2.right = &n5;
    n3.right = &n6;

    int result = widthOfBinaryTree(&n1);
    printf("%d\n", result);
    return 0;
}

A 3

B 4

C 5

D 6

💡 Hint

Think about the maximum number of nodes between the leftmost and rightmost nodes at any level.

The maximum width is the largest number of nodes between the leftmost and rightmost nodes at any level, counting nulls in between. Here, the maximum width is 4 at the third level.

🧠 Conceptual

intermediate

Understanding Indexing in Maximum Width Calculation

Why do we subtract the start index from each node's index before enqueueing children in the maximum width calculation?

A To prevent integer overflow by keeping indices small

B To sort the nodes at each level in ascending order

C To count only non-null nodes at each level

D To skip nodes that have no children

💡 Hint

Consider what happens to indices as the tree depth increases.

Subtracting the start index keeps the indices relative and small, preventing overflow when the tree is very deep.

🔧 Debug

advanced

Identify the Error in Width Calculation

What error will the following code produce when calculating the maximum width of a binary tree?

DSA C

int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    unsigned long long maxWidth = 0;
    Queue q = {NULL, NULL};
    enqueue(&q, root, 0ULL);

    while (!isEmpty(&q)) {
        int size = 0;
        QueueNode* temp = q.front;
        while (temp) {
            size++;
            temp = temp->next;
        }

        unsigned long long start = q.front->index;
        unsigned long long end = q.rear->index;
        if (end - start + 1 > maxWidth) maxWidth = end - start + 1;

        for (int i = 0; i < size; i++) {  // Note the <= here changed to <
            TreeNode* node = q.front->node;
            unsigned long long idx = q.front->index;
            dequeue(&q);
            if (node->left) enqueue(&q, node->left, 2 * (idx - start));
            if (node->right) enqueue(&q, node->right, 2 * (idx - start) + 1);
        }
    }
    return (int)maxWidth;
}

A Incorrect maximum width calculation

B No error, code runs correctly

C Compilation error due to syntax

D Segmentation fault due to dequeue on empty queue

💡 Hint

Check the loop boundary condition carefully.

The for loop uses <= size, causing one extra dequeue call when the queue is empty, leading to a segmentation fault.

📝 Syntax

advanced

Syntax Error in Queue Implementation

Which option contains a syntax error in the queue enqueue function?

DSA C

void enqueue(Queue* q, TreeNode* node, unsigned long long index) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    newNode->node = node;
    newNode->index = index;
    newNode->next = NULL;
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
}

A Missing return statement in void function

B Incorrect cast of malloc return value

C Missing semicolon after q->rear->next = newNode

D Using NULL instead of nullptr

💡 Hint

Look carefully at the lines inside the else block.

The line 'q->rear->next = newNode' is missing a semicolon, causing a syntax error.

🚀 Application

expert

Maximum Width with Sparse Tree

Given a binary tree where only the leftmost and rightmost nodes exist at the last level, what is the maximum width returned by the algorithm?

DSA C

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

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {2, NULL, NULL};
TreeNode n3 = {3, NULL, NULL};
TreeNode n4 = {4, NULL, NULL};
TreeNode n5 = {5, NULL, NULL};
n1.left = &n2;
n1.right = &n3;
n2.left = &n4;
n3.right = &n5;

int result = widthOfBinaryTree(&n1);
printf("%d\n", result);

A 4

B 2

C 5

D 3

💡 Hint

Remember the algorithm counts nulls between leftmost and rightmost nodes at each level.

At the last level, nodes 4 and 5 are at positions 0 and 3 respectively, so width = 3 - 0 + 1 = 4.

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