Maximum Width of Binary Tree in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the maximum width of a binary tree?

The maximum width is the largest number of nodes present at any single level (depth) of the binary tree.

intermediate

How can we track node positions to calculate the maximum width of a binary tree?

Assign an index to each node as if the tree was a complete binary tree: root = 0, left child = 2 * parent_index + 1, right child = 2 * parent_index + 2. This helps measure width by subtracting minimum from maximum indices at each level.

beginner

What data structure is commonly used to traverse levels of a binary tree for width calculation?

A queue is used for level order traversal (breadth-first search) to visit nodes level by level and track their positions.

intermediate

Why do we subtract the minimum index from the maximum index at each level when finding the width?

Because node indices may not start at zero for each level, subtracting the minimum index normalizes positions to avoid large gaps and gives the actual width as (max_index - min_index + 1).

beginner

What is the time complexity of finding the maximum width of a binary tree using level order traversal?

The time complexity is O(n), where n is the number of nodes, because each node is visited once during the traversal.

What does the maximum width of a binary tree represent?

A The total number of nodes

B The height of the tree

C The depth of the deepest leaf

D The number of nodes at the widest level

Maximum width is the count of nodes at the level with the most nodes.

Which traversal method is best suited to find the maximum width of a binary tree?

A Level order traversal (BFS)

B Preorder traversal

C Inorder traversal

D Postorder traversal

Level order traversal visits nodes level by level, which helps count nodes per level.

How are node indices assigned to calculate width in a binary tree?

A Root = 0; left child = 2 * parent + 1; right child = 2 * parent + 2

B Root = 1; left child = parent + 1; right child = parent + 2

C Root = 0; left child = parent - 1; right child = parent + 1

D Root = 1; left child = 2 * parent; right child = 2 * parent + 1

This indexing simulates a complete binary tree to measure width accurately.

Why do we add 1 after subtracting min index from max index to get width?

A To count only leaf nodes

B To correct for zero-based indexing

C Because width counts nodes inclusively between min and max indices

D To adjust for tree height

Width includes both ends, so we add 1 to count all nodes in the range.

What is the space complexity of the maximum width calculation using a queue?

A O(n^2), quadratic space

B O(n), where n is the maximum number of nodes at any level

C O(log n), where n is total nodes

D O(1), constant space

The queue holds nodes of one level at a time, which can be up to the maximum width.

Explain how to calculate the maximum width of a binary tree using level order traversal and node indexing.

Think about visiting nodes level by level and numbering them.

Describe why indexing nodes like a complete binary tree helps in finding the maximum width.

Imagine numbering seats in a theater row even if some are empty.

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