Maximum Width of Binary Tree in DSA Python - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: You are working on a program that analyzes the structure of a binary tree. One important measure is the maximum width of the tree, which is the largest number of nodes present at any single level.Imagine a family tree where you want to find the generation with the most members.

🎯 Goal: Build a program that calculates the maximum width of a given binary tree using level order traversal.

📋 What You'll Learn

Create a binary tree using the given Node class

Use a queue to perform level order traversal

Calculate the width of each level

Find and print the maximum width

💡 Why This Matters

🌍 Real World

Calculating the maximum width of a binary tree helps in understanding the structure and balance of hierarchical data like organizational charts or file systems.

💼 Career

This concept is useful for software engineers working with tree data structures, such as in databases, compilers, or network routing algorithms.

1

Create the Binary Tree Nodes

Create the binary tree nodes using the Node class exactly as follows: root node with value 1, root's left child with value 3, root's right child with value 2, left child's left child with value 5, and left child's right child with value 3.

DSA Python

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

# Create the binary tree nodes as described
# Your code here

Hint

Use the Node class to create nodes and assign them to root and its children exactly as specified.

2

Initialize the Queue for Level Order Traversal

Create a list called queue and initialize it with the root node to start the level order traversal.

DSA Python

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

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

# Initialize the queue with root node
# Your code here

Hint

Use a list named queue and put the root node inside it to start.

3

Calculate Maximum Width Using Level Order Traversal

Create a variable max_width set to 0. Use a while loop that runs while queue is not empty. Inside the loop, find the length of queue and store it in level_length. Update max_width to be the maximum of max_width and level_length. Then, use a for loop to iterate level_length times, popping the first node from queue. For each popped node, if it has a left child, append it to queue. If it has a right child, append it to queue.

DSA Python

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

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

queue = [root]

# Calculate max_width using level order traversal
# Your code here

Hint

Use a while loop to process each level. Use len(queue) to get the number of nodes at the current level. Update max_width accordingly. Then pop nodes and add their children to the queue.

4

Print the Maximum Width

Print the value of max_width.

DSA Python

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

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

queue = [root]
max_width = 0
while queue:
    level_length = len(queue)
    max_width = max(max_width, level_length)
    for _ in range(level_length):
        node = queue.pop(0)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# Print the maximum width
# Your code here

Hint

Use print(max_width) to show the result.

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