Maximum Width of Binary Tree in DSA Python - Time & Space Complexity

Time Complexity: Maximum Width of Binary Tree

O(n)

Understanding Time Complexity

We want to know how the time needed to find the maximum width of a binary tree changes as the tree grows.

How does the number of nodes affect the work done to find the widest level?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

from collections import deque

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

This code finds the maximum width of a binary tree by traversing each level and tracking node positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that visits each node once.
• How many times: Once for each node in the tree (n times).

How Execution Grows With Input

As the number of nodes grows, the code visits each node once, so the work grows directly with the number of nodes.

Input Size (n)	Approx. Operations
10	About 10 visits
100	About 100 visits
1000	About 1000 visits

Pattern observation: The work grows linearly as the tree size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum width grows in direct proportion to the number of nodes in the tree.

Common Mistake

[X] Wrong: "The time depends on the height of the tree only."

[OK] Correct: The code must visit every node to check widths, so it depends on total nodes, not just height.

Interview Connect

Understanding this helps you explain how tree traversals work and how to measure properties like width efficiently.

Self-Check

"What if we used a recursive approach instead of a queue? How would the time complexity change?"

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