Maximum Width of Binary Tree in DSA C

Mental Model

We want to find the widest level in a tree by counting nodes including gaps between them.

Analogy: Imagine a family tree where some members are missing; the width counts all spots from leftmost to rightmost member, even empty seats.

       1
      / \
     3   2
    /     \
   5       9
  /         \
 6           7

Dry Run Walkthrough

Input: Binary tree: 1 -> 3,2 -> 5,null,null,9 -> 6,null,null,null,null,null,7

Goal: Find the maximum width of the tree including null gaps between nodes at the widest level.

Step 1: Start level order traversal with root node 1 at index 0

[(1,0)]

Why: We assign index 0 to root to track positions for width calculation

Step 2: Process level 1: nodes [(1,0)], add children (3,1) and (2,2)

[(3,1), (2,2)]

Why: Children get indices 2*parent_index+1 and 2*parent_index+2 to keep track of positions

Step 3: Calculate width at level 1: 2 - 1 + 1 = 2

Width = 2

Why: Width is rightmost index minus leftmost plus one

Step 4: Process level 2: nodes [(3,1), (2,2)], add children (5,3), (null), (null), (9,6)

[(5,3), (9,6)]

Why: Null children are skipped, indices keep track of gaps

Step 5: Calculate width at level 2: 6 - 3 + 1 = 4

Width = 4

Why: This level is wider due to gaps between nodes

Step 6: Process level 3: nodes [(5,3), (9,6)], add children (6,7), (null), (null), (7,14)

[(6,7), (7,14)]

Why: Indices reflect positions including gaps

Step 7: Calculate width at level 3: 14 - 7 + 1 = 8

Width = 8

Why: This is the maximum width found

Result:

Maximum width = 8

Annotated Code

DSA C

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

// Define binary tree node
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Queue node to hold tree node and its index
typedef struct QueueNode {
    TreeNode *node;
    unsigned long long index;
} QueueNode;

// Simple queue for BFS
typedef struct Queue {
    QueueNode *data;
    int front;
    int rear;
    int capacity;
} Queue;

Queue* createQueue(int capacity) {
    Queue *q = (Queue*)malloc(sizeof(Queue));
    q->data = (QueueNode*)malloc(sizeof(QueueNode) * capacity);
    q->front = 0;
    q->rear = 0;
    q->capacity = capacity;
    return q;
}

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

void enqueue(Queue *q, TreeNode *node, unsigned long long index) {
    q->data[q->rear].node = node;
    q->data[q->rear].index = index;
    q->rear++;
}

QueueNode dequeue(Queue *q) {
    return q->data[q->front++];
}

// Function to find maximum width of binary tree
int widthOfBinaryTree(TreeNode* root) {
    if (!root) return 0;
    int maxWidth = 0;
    Queue *q = createQueue(1000);
    enqueue(q, root, 0ULL); // root index 0

    while (!isEmpty(q)) {
        int size = q->rear - q->front;
        unsigned long long leftIndex = q->data[q->front].index;
        unsigned long long rightIndex = leftIndex; // initialize

        for (int i = 0; i < size; i++) {
            QueueNode curr = dequeue(q);
            TreeNode *node = curr.node;
            unsigned long long idx = curr.index - leftIndex; // normalize to prevent overflow

            if (node->left) enqueue(q, node->left, 2 * idx + 1);
            if (node->right) enqueue(q, node->right, 2 * idx + 2);

            if (i == size - 1) rightIndex = curr.index;
        }

        int width = (int)(rightIndex - leftIndex + 1);
        if (width > maxWidth) maxWidth = width;
    }

    free(q->data);
    free(q);
    return maxWidth;
}

// Helper to create new node
TreeNode* newNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    // Build tree from dry run example
    TreeNode *root = newNode(1);
    root->left = newNode(3);
    root->right = newNode(2);
    root->left->left = newNode(5);
    root->right->right = newNode(9);
    root->left->left->left = newNode(6);
    root->right->right->right = newNode(7);

    int maxWidth = widthOfBinaryTree(root);
    printf("Maximum width = %d\n", maxWidth);
    return 0;
}

enqueue(q, root, 0ULL);

Start BFS with root at index 0 to track positions

int size = q->rear - q->front;

Get number of nodes at current level

unsigned long long leftIndex = q->data[q->front].index;

Record leftmost index at this level

unsigned long long idx = curr.index - leftIndex;

Normalize indices to avoid overflow and keep relative positions

if (node->left) enqueue(q, node->left, 2 * idx + 1);

Add left child with calculated index

if (node->right) enqueue(q, node->right, 2 * idx + 2);

Add right child with calculated index

int width = (int)(rightIndex - leftIndex + 1);

Calculate width of current level

if (width > maxWidth) maxWidth = width;

Update max width if current level is wider

Output

Maximum width = 8

Complexity Analysis

Time: O(n) because we visit each node once during level order traversal

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Naive approach might store all nodes including nulls explicitly, increasing space; this method uses indices to track gaps efficiently

Edge Cases

Empty tree

Returns width 0 as there are no nodes

DSA C

if (!root) return 0;

Tree with single node

Returns width 1 as only root exists

DSA C

enqueue(q, root, 0ULL);

Tree with missing children causing gaps

Indices track positions correctly to count gaps in width

DSA C

unsigned long long idx = curr.index - leftIndex;

When to Use This Pattern

When asked for the widest level in a tree including empty spots, use level order traversal with position indices to track gaps and calculate width.

Common Mistakes

Mistake: Not normalizing indices causing integer overflow on deep trees
Fix: Subtract leftmost index at each level from all indices to keep them small

Mistake: Counting only existing nodes ignoring gaps, leading to wrong width
Fix: Use indices to include gaps between nodes in width calculation

Summary

Finds the maximum width of a binary tree including gaps between nodes at each level.

Use when you need to measure the widest level of a tree counting empty positions as well.

Track node positions with indices during level order traversal to capture gaps and calculate width.

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