Maximum Width of Binary Tree in DSA C - Time & Space Complexity

Time Complexity: Maximum Width of Binary Tree

O(n)

Understanding Time Complexity

We want to understand how the time needed to find the maximum width of a binary tree changes as the tree grows.

Specifically, how does the number of nodes affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Calculate maximum width of a binary tree
int maxWidth(struct TreeNode* root) {
    if (!root) return 0;
    int maxWidth = 0;
    struct Queue* q = createQueue();
    enqueue(q, root);
    while (!isEmpty(q)) {
        int count = queueSize(q);
        maxWidth = max(maxWidth, count);
        for (int i = 0; i < count; i++) {
            struct TreeNode* node = dequeue(q);
            if (node->left) enqueue(q, node->left);
            if (node->right) enqueue(q, node->right);
        }
    }
    return maxWidth;
}
    

This code finds the maximum number of nodes at any level in the binary tree by visiting each node once.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node once in a breadth-first manner.
• How many times: Each node is enqueued and dequeued exactly once.

How Execution Grows With Input

As the number of nodes increases, the code visits each node once, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows linearly as the tree size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum width grows directly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The time depends on the height of the tree only."

[OK] Correct: The code visits every node, not just levels, so total nodes matter more than height alone.

Interview Connect

Understanding how to analyze tree traversal time helps you explain your approach clearly and confidently in interviews.

Self-Check

"What if we used depth-first search instead of breadth-first search? How would the time complexity change?"

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