Maximum Width of Binary Tree in DSA C#

Mental Model

We want to find the widest level in a tree by counting nodes including gaps between them.

Analogy: Imagine a family tree where some branches have missing members; we count the widest generation including empty spots.

       1
      / \
     3   2
    /     \
   5       9
  /         \
 6           7

Dry Run Walkthrough

Input: Binary tree: 1 -> 3,2 -> 5,null,null,9 -> 6,null,null,7

Goal: Find the maximum width of the tree including null gaps between nodes at each level

Step 1: Start at root node 1 with index 0

[(1,0)]

Why: We assign index 0 to root to track positions for width calculation

Step 2: Process level 1: nodes [(1,0)]

Level width = 0 - 0 + 1 = 1

Why: Only root node, width is 1

Step 3: Add children of 1: left child 3 with index 0*2=0, right child 2 with index 0*2+1=1

[(3,0), (2,1)]

Why: Assign indices to children to keep track of positions

Step 4: Process level 2: nodes [(3,0), (2,1)]

Level width = 1 - 0 + 1 = 2

Why: Width is distance between leftmost and rightmost indices plus one

Step 5: Add children of 3 and 2: 3's left child 5 at 0*2=0, 3's right child null, 2's left child null, 2's right child 9 at 1*2+1=3

[(5,0), (9,3)]

Why: Null children are skipped, indices keep track of gaps

Step 6: Process level 3: nodes [(5,0), (9,3)]

Level width = 3 - 0 + 1 = 4

Why: Width includes gap between indices 0 and 3

Step 7: Add children of 5 and 9: 5's left child 6 at 0*2=0, 5's right null, 9's left null, 9's right child 7 at 3*2+1=7

[(6,0), (7,7)]

Why: Indices show wide gap between nodes

Step 8: Process level 4: nodes [(6,0), (7,7)]

Level width = 7 - 0 + 1 = 8

Why: Maximum width found including gaps

Result:

Maximum width = 8

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    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 levelSize = queue.Count;
            int levelHeadIndex = queue.Peek().index; // index of first node at this level
            int firstIndex = 0, lastIndex = 0;

            for (int i = 0; i < levelSize; i++) {
                var (node, index) = queue.Dequeue();
                int currIndex = index - levelHeadIndex; // normalize to prevent overflow
                if (i == 0) firstIndex = currIndex;
                if (i == levelSize - 1) lastIndex = currIndex;

                if (node.left != null) queue.Enqueue((node.left, currIndex * 2));
                if (node.right != null) queue.Enqueue((node.right, currIndex * 2 + 1));
            }

            int width = lastIndex - firstIndex + 1;
            if (width > maxWidth) maxWidth = width;
        }

        return maxWidth;
    }

    public static void Main() {
        // Build tree: 1
        //           /   \
        //          3     2
        //         /       \
        //        5         9
        //       /           \
        //      6             7
        TreeNode root = new TreeNode(1,
            new TreeNode(3,
                new TreeNode(5,
                    new TreeNode(6), null),
                null),
            new TreeNode(2,
                null,
                new TreeNode(9,
                    null,
                    new TreeNode(7))));

        Solution sol = new Solution();
        int maxWidth = sol.WidthOfBinaryTree(root);
        Console.WriteLine(maxWidth);
    }
}

queue.Enqueue((root, 0));

Start BFS with root node at index 0

int levelHeadIndex = queue.Peek().index;

Record index of first node at current level to normalize indices

int currIndex = index - levelHeadIndex;

Normalize current node index to prevent integer overflow

if (node.left != null) queue.Enqueue((node.left, currIndex * 2));

Assign left child index as 2 * current index

if (node.right != null) queue.Enqueue((node.right, currIndex * 2 + 1));

Assign right child index as 2 * current index + 1

int width = lastIndex - firstIndex + 1;

Calculate width of current level including gaps

if (width > maxWidth) maxWidth = width;

Update maximum width if current level is wider

Output

8

Complexity Analysis

Time: O(n) because we visit each node once during level order traversal

Space: O(n) because the queue can hold up to all nodes at the widest level

vs Alternative: Compared to naive approach that might store all nodes including nulls explicitly, this method uses indices to track gaps efficiently without extra space for nulls

Edge Cases

Empty tree

Returns width 0 immediately

DSA C#

if (root == null) return 0;

Single node tree

Returns width 1 as only root exists

DSA C#

queue.Enqueue((root, 0));

Tree with only left children

Width is always 1 at each level

DSA C#

if (node.left != null) queue.Enqueue((node.left, currIndex * 2));

When to Use This Pattern

When asked to find the widest level in a tree including gaps, use BFS with index tracking to measure width efficiently.

Common Mistakes

Mistake: Not normalizing indices each level causing integer overflow
Fix: Subtract levelHeadIndex from each node's index at current level to keep indices small

Mistake: Counting only existing nodes ignoring gaps, leading to wrong width
Fix: Use indices to include gaps between nodes when calculating width

Summary

Finds the maximum width of a binary tree including gaps between nodes at each level.

Use when you need to measure the widest level in a tree considering missing nodes.

Track node positions with indices during BFS and normalize each level to avoid overflow.

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