Maximum Width of Binary Tree in DSA C - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: Imagine you are working with a binary tree that represents a company's organizational chart. You want to find the maximum number of employees at any level in the hierarchy.

🎯 Goal: Build a program in C that calculates the maximum width of a binary tree. The width is the maximum number of nodes present at any level of the tree.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a queue to traverse the tree level by level

Calculate the width of each level

Print the maximum width found

💡 Why This Matters

🌍 Real World

Finding the maximum width of a binary tree helps understand the widest level in hierarchical data like organizational charts or file systems.

💼 Career

This concept is useful for software engineers working with tree data structures, such as in databases, compilers, or network routing.

1

Create the Binary Tree Structure

Define a struct Node with int data, Node* left, and Node* right. Then create nodes to build this exact tree:
1
/ \
2 3
/ \
4 5

DSA C

// Define struct Node and create the tree nodes
// Your code here

Hint

Start by defining the node structure and a helper function to create new nodes. Then build the tree exactly as shown.

2

Set Up a Queue for Level Order Traversal

Create a queue structure using an array or linked list to hold Node*. Define enqueue and dequeue functions. Initialize the queue and enqueue the root node.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Define queue structure and functions here
// Your code here

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->right = newNode(5);

    // Initialize queue and enqueue root
    // Your code here
    return 0;
}

Hint

Use an array-based queue with front and rear indexes. Enqueue the root node to start level order traversal.

3

Calculate Maximum Width Using Level Order Traversal

Use a while loop to process nodes level by level from the queue. For each level, count the number of nodes currently in the queue. Update a variable maxWidth if this count is greater. Enqueue the left and right children of each node if they exist.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

#define MAX_QUEUE_SIZE 100

typedef struct Queue {
    Node* items[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

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

void enqueue(Queue* q, Node* node) {
    if (q->rear items[q->rear++] = node;
    }
}

Node* dequeue(Queue* q) {
    if (!isEmpty(q)) {
        return q->items[q->front++];
    }
    return NULL;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->right = newNode(5);

    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    int maxWidth = 0;

    // Use a while loop to traverse levels and update maxWidth
    // Your code here

    return 0;
}

Hint

Count nodes at each level by checking queue size before processing that level. Update maxWidth if current level is wider.

4

Print the Maximum Width

Add a printf statement to display the maximum width stored in maxWidth.

DSA C

#include 
#include 

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

#define MAX_QUEUE_SIZE 100

typedef struct Queue {
    Node* items[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

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

void enqueue(Queue* q, Node* node) {
    if (q->rear items[q->rear++] = node;
    }
}

Node* dequeue(Queue* q) {
    if (!isEmpty(q)) {
        return q->items[q->front++];
    }
    return NULL;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->right->right = newNode(5);

    Queue q;
    initQueue(&q);
    enqueue(&q, root);

    int maxWidth = 0;

    while (!isEmpty(&q)) {
        int levelSize = q.rear - q.front;
        if (levelSize > maxWidth) {
            maxWidth = levelSize;
        }

        for (int i = 0; i left != NULL) {
                enqueue(&q, current->left);
            }
            if (current->right != NULL) {
                enqueue(&q, current->right);
            }
        }
    }

    // Print the maximum width
    // Your code here

    return 0;
}

Hint

Use printf to show the value of maxWidth after the traversal.

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