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

Time Complexity: Maximum Width of Binary Tree

O(n)

Understanding Time Complexity

We want to understand 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 by the algorithm?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

public int WidthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    int maxWidth = 0;
    var queue = new Queue<(TreeNode node, int index)>();
    queue.Enqueue((root, 0));
    while (queue.Count > 0) {
        int count = queue.Count;
        int start = queue.Peek().index;
        int end = start;
        for (int i = 0; i < count; i++) {
            var (node, index) = queue.Dequeue();
            end = index;
            if (node.left != null) queue.Enqueue((node.left, 2 * index));
            if (node.right != null) queue.Enqueue((node.right, 2 * index + 1));
        }
        maxWidth = Math.Max(maxWidth, end - start + 1);
    }
    return maxWidth;
}
    

This code finds the maximum width of a binary tree by level-order traversal, tracking node positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop runs once per tree level, and the inner for loop processes all nodes at that level.
• How many times: Each node is enqueued and dequeued exactly once, so the total operations scale with the number of nodes.

How Execution Grows With Input

As the number of nodes (n) increases, the algorithm visits each node once.

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

Pattern observation: The work grows roughly in direct proportion to the number of nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the maximum width grows linearly with the number of nodes in the tree.

Common Mistake

[X] Wrong: "The algorithm checks every possible pair of nodes, so it must be quadratic time."

[OK] Correct: The algorithm only visits each node once in a level order, so it does not compare all pairs, keeping the time linear.

Interview Connect

Understanding this linear time approach shows you can efficiently process tree levels, a common skill in many coding problems.

Self-Check

"What if we used a depth-first search instead of breadth-first search? How would the time complexity change?"

Practice

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

easy

A. The number of leaf nodes in the tree

B. The height of the tree from root to the deepest leaf

C. The total number of nodes in the tree

D. The largest number of nodes present at any single level of the tree

Solution

1. Step 1: Understand the definition of width in a binary tree

   The width is the count of nodes at the widest level of the tree.

2. Step 2: Compare with other tree properties

   Height is depth, total nodes is size, leaves are end nodes, none represent width.

3. Final Answer:

   The largest number of nodes present at any single level of the tree -> Option D

4. Quick Check:

   Width = max nodes at one level [OK]

Hint: Width means max nodes at one level, not height or total nodes [OK]

Common Mistakes:

• Confusing width with height
• Thinking width is total nodes
• Mixing width with leaf count

2. Which C# data structure is best suited to help calculate the maximum width of a binary tree level by level?

easy

A. Queue

B. Stack

C. Dictionary

D. List

Solution

1. Step 1: Identify traversal method for level-wise processing

   Level order traversal uses a queue to process nodes level by level.

2. Step 2: Match data structure to traversal

   Queue supports FIFO, perfect for breadth-first search to measure width.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Queue = level order traversal tool [OK]

Hint: Use queue for level order traversal to measure width [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Choosing dictionary which stores key-value pairs, not order
• Using list without queue behavior

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

public class TreeNode {
    public int val;
    public TreeNode left, right;
    public TreeNode(int v) { val = v; }
}

// Tree structure:
//       1
//      / \
//     2   3
//    /     \
//   4       5

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.right = new TreeNode(5);

int MaxWidth(TreeNode root) {
    if (root == null) return 0;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int maxWidth = 0;
    while (queue.Count > 0) {
        int count = queue.Count;
        maxWidth = Math.Max(maxWidth, count);
        for (int i = 0; i < count; i++) {
            var node = queue.Dequeue();
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return maxWidth;
}

Console.WriteLine(MaxWidth(root));

medium

A. 1

B. 3

C. 2

D. 4

Solution

1. Step 1: Analyze tree levels and node counts

   Level 1: 1 node (1), Level 2: 2 nodes (2,3), Level 3: 2 nodes (4,5).

2. Step 2: Determine maximum width from levels

   Maximum width is 2 at levels 2 and 3.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   Max width = 2 nodes at widest level [OK]

Hint: Count nodes per level, max count is width [OK]

Common Mistakes:

• Counting total nodes instead of per level
• Confusing width with tree height
• Ignoring null children in width calculation

4. Identify the bug in this C# method that attempts to find the maximum width of a binary tree:

int MaxWidth(TreeNode root) {
    if (root == null) return 0;
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    int maxWidth = 0;
    while (queue.Count > 0) {
        int count = queue.Count;
        maxWidth = Math.Max(maxWidth, count);
        for (int i = 0; i <= count; i++) {
            var node = queue.Dequeue();
            if (node.left != null) queue.Enqueue(node.left);
            if (node.right != null) queue.Enqueue(node.right);
        }
    }
    return maxWidth;
}

medium

A. The maxWidth should be updated after the for loop

B. The for loop condition should be i < count, not i <= count

C. The queue should be a stack for correct traversal

D. The method should return count instead of maxWidth

Solution

1. Step 1: Check for off-by-one error in loop

   The for loop runs from i = 0 to i <= count, which runs count+1 times causing dequeue error.

2. Step 2: Correct loop condition

   Change to i < count to run exactly count times matching queue size at start of loop.

3. Final Answer:

   The for loop condition should be i < count, not i <= count -> Option B

4. Quick Check:

   Loop runs count times, not count+1 [OK]

Hint: For loops over queue size use i < count, not i <= count [OK]

Common Mistakes:

• Using <= instead of < causing runtime errors
• Replacing queue with stack breaking level order
• Updating maxWidth at wrong time

5. Given a binary tree where some nodes are missing (null), how can you modify the maximum width calculation to count the width including null positions between nodes? Example tree: // 1 // / \ // 2 3 // \ \ // 4 5 What approach correctly calculates the maximum width as 3 for this tree?

hard

A. Assign position indices to nodes and calculate width as max index difference + 1 per level

B. Count only non-null nodes at each level ignoring gaps

C. Use depth-first traversal and count leaf nodes

D. Calculate width as total nodes minus null nodes

Solution

1. Step 1: Understand the problem with null gaps

   Simple counting ignores null gaps, so width underestimates actual spread.

2. Step 2: Use position indices to track node positions

   Assign indices like a heap: root=0, left=2*index+1, right=2*index+2, then width = max index - min index + 1 per level.

3. Step 3: Calculate width using indices

   This method counts null gaps, giving correct width of 3 in example.

4. Final Answer:

   Assign position indices to nodes and calculate width as max index difference + 1 per level -> Option A

5. Quick Check:

   Indexing nodes counts gaps, width = max-min+1 [OK]

Hint: Use node indices to include null gaps in width [OK]

Common Mistakes:

• Ignoring null gaps between nodes
• Counting only existing nodes per level
• Using DFS instead of BFS for width