Maximum Width of Binary Tree in DSA Python - Execution Trace

Concept Flow - Maximum Width of Binary Tree

Start at root node

↓

Initialize queue with (node, index=0)

↓

While queue not empty

↓

For each level: get size

↓

Track first and last index in level

↓

Calculate width = last - first + 1

↓

Update max width if current width is larger

↓

Add children to queue with updated indices

↓

Repeat for next level

↓

Return max width found

We traverse the tree level by level, tracking node positions to find the widest level.

Execution Sample

DSA Python

def widthOfBinaryTree(root):
    max_width = 0
    queue = [(root, 0)]
    while queue:
        level_length = len(queue)
        _, first_index = queue[0]
        for _ 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))
        _, last_index = queue[-1] if queue else (None, index)
        max_width = max(max_width, last_index - first_index + 1)
    return max_width

This code finds the maximum width of a binary tree by level order traversal with position indices.

Execution Table

Step	Operation	Nodes in Queue (node, index)	First Index	Last Index	Width Calculated	Max Width	Visual Tree State
1	Initialize queue with root	[(1,0)]	0	0	1	1	1(0)
2	Process level 1	[(1,0)]	0	0	1	1	1(0)
3	Add children of 1	[(2,0),(3,1)]	0	1	2	2	1(0) ├─2(0) └─3(1)
4	Process level 2	[(2,0),(3,1)]	0	1	2	2	1(0) ├─2(0) └─3(1)
5	Add children of 2 and 3	[(4,0),(5,1),(7,3)]	0	3	4	4	1(0) ├─2(0) │ ├─4(0) │ └─5(1) └─3(1) └─7(3)
6	Process level 3	[(4,0),(5,1),(7,3)]	0	3	4	4	1(0) ├─2(0) │ ├─4(0) │ └─5(1) └─3(1) └─7(3)
7	Add children of 4,5,7 (none)	[]	-	-	-	4	1(0) ├─2(0) │ ├─4(0) │ └─5(1) └─3(1) └─7(3)
8	Queue empty, end	[]	-	-	-	4	Final max width = 4

💡 Queue is empty, all levels processed, max width found is 4

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
max_width	0	2	4	4	4
queue	[(1,0)]	[(2,0),(3,1)]	[(4,0),(5,1),(7,3)]	[]	[]
level_length	-	2	3	-	-
width	-	2	4	-	-

Key Moments - 3 Insights

Why do we assign indices to nodes in the queue?

Indices represent the node's position in a perfect binary tree, allowing calculation of width even if nodes are missing. See execution_table rows 3,5 where indices help find width.

Why do we calculate width as last - first + 1?

Because indices start at 0, width counts all positions between first and last inclusive. This is shown in execution_table rows 3,5,6 where width is computed.

What happens if a node has no children?

No new nodes are added to the queue for that node, so the queue shrinks until empty, ending the loop. See execution_table row 7 where no children are added.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what is the width calculated for that level?

A 4

B 3

C 2

D 1

💡 Hint

Check the 'Width Calculated' column at Step 5 in execution_table.

At which step does the max_width first update to 2?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at the 'Max Width' column in execution_table and find when it changes from 1 to 2.

If the root had no children, what would be the max width returned?

A 2

B 0

C 1

D Undefined

💡 Hint

Refer to variable_tracker for max_width starting value and queue initialization.

Concept Snapshot

Maximum Width of Binary Tree:
- Use level order traversal with a queue
- Assign indices to nodes as if in a perfect tree
- Width = last index - first index + 1 per level
- Track max width across all levels
- Return max width after traversal

Full Transcript

To find the maximum width of a binary tree, we do a level order traversal using a queue. Each node is paired with an index representing its position in a perfect binary tree. For each level, we find the first and last indices of nodes and calculate the width as last minus first plus one. We update the maximum width if the current level's width is larger. We add children to the queue with updated indices and continue until the queue is empty. The final maximum width is returned.

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