Maximum Width of Binary Tree in DSA Python - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the root node and its index 0.

DSA Python

queue = [(root, [1])]

Drag options to blanks, or click blank then click option'

A0

Broot

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting index at 1 instead of 0 causes off-by-one errors.

Using the root node itself as index causes type errors.

The root node is assigned index 0 to start the level indexing from zero.

2fill in blank

medium

Complete the code to update the maximum width after processing each level.

DSA Python

max_width = max(max_width, [1] - min_index + 1)

Drag options to blanks, or click blank then click option'

Amin_index

Blevel_length

Cmax_index

Dwidth

Attempts:

3 left

💡 Hint

Common Mistakes

Using min_index instead of max_index causes negative or zero width.

Forgetting to add 1 leads to off-by-one errors.

Width is calculated as max_index - min_index + 1 for the current level.

3fill in blank

hard

Fix the error in the code that appends the left child with its correct index.

DSA Python

if node.left:
    queue.append((node.left, [1] * 2))

Drag options to blanks, or click blank then click option'

Anode

Bindex

Cmax_width

Dmax_index

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' instead of 'index' causes type errors.

Using max_width or max_index instead of parent's index causes wrong indexing.

The left child's index is 2 * parent's index, so we use 'index' here.

4fill in blank

hard

Fill both blanks to append the right child with its correct index and update the queue.

DSA Python

if node.right:
    queue.append((node.right, [1] * 2 + [2]))

Drag options to blanks, or click blank then click option'

Aindex

B1

C0

Dmax_width

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of 1 for the offset causes wrong indexing.

Using max_width instead of index causes errors.

Right child's index is 2 * parent's index + 1, so blanks are 'index' and '1'.

5fill in blank

hard

Fill all three blanks to complete the while loop that processes each level and updates max_width.

DSA Python

while queue:
    level_length = len(queue)
    min_index = queue[0][1]
    max_index = queue[-1][[1]]
    for _ in range(level_length):
        node, index = queue.pop(0)
        if node.left:
            queue.append((node.left, index * 2 + [2]))
        if node.right:
            queue.append((node.right, index * 2 + [3]))
    max_width = max(max_width, max_index - min_index + 1)

Drag options to blanks, or click blank then click option'

A1

B0

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong tuple index for max_index causes errors.

Swapping offsets for left and right children causes wrong indexing.

max_index is at position 1 in tuple, left child index offset is 0, right child offset is 1.

Practice

1. What does the "maximum width" of a binary tree represent?

easy

A. The total number of nodes in the tree

B. The height of the tree

C. The maximum number of nodes present at any level of the tree

D. The sum of values of nodes at the widest level

Solution

1. Step 1: Understand the term "width" in binary trees

   The width of a binary tree at a level is the count of nodes present at that level.

2. Step 2: Define maximum width

   The maximum width is the largest such count among all levels of the tree.

3. Final Answer:

   The maximum number of nodes present at any level of the tree -> Option C

4. Quick Check:

   Width means node count per level = maximum width [OK]

Hint: Maximum width = max nodes in any single level [OK]

Common Mistakes:

• Confusing width with height
• Counting total nodes instead of per level
• Summing node values instead of counting nodes

2. Which of the following Python code snippets correctly initializes a queue to help find the maximum width of a binary tree?

easy

A. queue = [(root, 0)]

B. queue = [root]

C. queue = root

D. queue = []

Solution

1. Step 1: Understand queue usage in width calculation

   We use a queue to hold nodes along with their position indices to track width.

2. Step 2: Check correct initialization

   Initializing queue as a list of tuples with (node, index) is correct: [(root, 0)].

3. Final Answer:

   queue = [(root, 0)] -> Option A

4. Quick Check:

   Queue holds (node, index) pairs = correct initialization [OK]

Hint: Use (node, index) pairs in queue for width tracking [OK]

Common Mistakes:

• Using queue = [root] without index
• Assigning queue = root (not a list)
• Starting with empty queue []

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

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = [(root, 0)]
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for i in range(level_length):
            node, index = queue.pop(0)
            if node.left:
                queue.append((node.left, 2 * index))
            if node.right:
                queue.append((node.right, 2 * index + 1))
        max_width = max(max_width, index - first_index + 1)
    return max_width

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.right.right = Node(5)
print(widthOfBinaryTree(root))

medium

A. 3

B. 2

C. 5

D. 4

Solution

1. Step 1: Trace the tree structure and indices

   Level 0: Node 1 at index 0 (width 1) Level 1: Nodes 2 (index 0), 3 (index 1) width = 2 Level 2: Nodes 4 (index 0), 5 (index 3) width = 3 - 0 + 1 = 4

2. Step 2: Calculate max width

   Maximum width is 4 at level 2.

3. Final Answer:

   4 -> Option D

4. Quick Check:

   Max width = 4 nodes wide at level 2 [OK]

Hint: Track indices to find width = last - first + 1 [OK]

Common Mistakes:

• Ignoring index gaps causing wrong width
• Using length of queue directly as width
• Not updating max_width correctly

4. Identify the bug in this code snippet that attempts to find the maximum width of a binary tree:

def widthOfBinaryTree(root):
    if not root:
        return 0
    max_width = 0
    queue = [(root, 0)]
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for i in range(level_length):
            node, index = queue.pop(0)
            if node.left:
                queue.append((node.left, index * 2 + 1))
            if node.right:
                queue.append((node.right, index * 2 + 2))
        max_width = max(max_width, index - first_index + 1)
    return max_width

medium

A. Left and right child indices are swapped; should be 2*index and 2*index+1

B. Queue should be a stack for correct traversal

C. max_width update is outside the while loop

D. Missing check for empty tree at start

Solution

1. Step 1: Check child index calculation

   Correct indices for left and right children are 2*index and 2*index+1 respectively.

2. Step 2: Identify incorrect index formula

   Code uses index*2+1 for left and index*2+2 for right, which is swapped and incorrect.

3. Final Answer:

   Left and right child indices are swapped; should be 2*index and 2*index+1 -> Option A

4. Quick Check:

   Child indices must be 2*i and 2*i+1 [OK]

Hint: Left child = 2*i, right child = 2*i+1 [OK]

Common Mistakes:

• Swapping left and right child indices
• Using stack instead of queue
• Updating max_width outside loop

5. Given a binary tree where some levels have missing nodes, which approach correctly calculates the maximum width including gaps between nodes?
Choose the best method to handle this scenario.

hard

A. Count only existing nodes at each level ignoring gaps

B. Use level order traversal with node indices to calculate width as last_index - first_index + 1

C. Calculate width as the maximum depth of the tree

D. Sum the values of nodes at each level and find the maximum sum

Solution

1. Step 1: Understand gaps in tree levels

   Missing nodes create gaps, so counting nodes alone misses width.

2. Step 2: Use indices to include gaps

   Assign indices to nodes as if tree was complete; width = last_index - first_index + 1.

3. Step 3: Apply level order traversal with indices

   This method captures true width including empty spaces between nodes.

4. Final Answer:

   Use level order traversal with node indices to calculate width as last_index - first_index + 1 -> Option B

5. Quick Check:

   Index-based width includes gaps = correct max width [OK]

Hint: Use indices to count gaps for true width [OK]

Common Mistakes:

• Ignoring gaps by counting nodes only
• Using tree depth as width
• Summing node values instead of counting width