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

Recall & Review

beginner

What does the 'maximum width' of a binary tree mean?

The maximum width of a binary tree is the largest (max_index - min_index + 1) at any single level (depth) of the tree, accounting for gaps between nodes.

beginner

Why do we use a queue in the algorithm to find the maximum width of a binary tree?

A queue helps us visit nodes level by level (breadth-first), tracking indices to compute the width of each level and find the maximum.

intermediate

In the maximum width problem, why do we assign an 'index' to each node during traversal?

Assigning an index to each node helps us calculate the width of the current level by subtracting the minimum index from the maximum index plus one, accounting for gaps caused by missing nodes.

intermediate

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 exactly once.

advanced

How does the algorithm handle missing nodes when calculating the maximum width?

By using indices for nodes as if the tree was a complete binary tree, the algorithm counts the gaps between nodes, ensuring the width includes spaces where nodes could be but are missing.

What data structure is commonly used to traverse a binary tree level by level?

A Hash Map

B Stack

C Queue

D Linked List

A queue is used for breadth-first traversal, which visits nodes level by level.

How do we calculate the width of a level in the binary tree when using node indices?

A max_index - min_index + 1

B max_index + min_index

C max_index - min_index

D min_index - max_index + 1

Width is calculated as max_index - min_index + 1 to include all nodes and gaps between them.

What does the maximum width of a binary tree represent?

A The height of the tree

B The maximum (max_index - min_index + 1) at any level

C The total number of nodes

D The depth of the deepest leaf

Maximum width is the largest positional width (max_index - min_index + 1) at any level, accounting for gaps.

If a binary tree has only one node, what is its maximum width?

A 1

B Undefined

C 2

D 0

A single node means the maximum width is 1 at that level.

Why do we normalize indices by subtracting the minimum index at each level?

A To sort the nodes

B To prevent integer overflow

C To count nodes only

D To keep indices small and avoid large numbers

Normalizing indices keeps them small and manageable during calculations.

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

Think about visiting nodes level by level and how indices help count gaps.

Describe why indexing nodes is important when calculating the maximum width of a binary tree with missing nodes.

Imagine the tree as a full grid with empty spots.

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