Maximum Width of Binary Tree in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation

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

DSA C#

using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left, 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;
        Queue<(TreeNode node, int index)> queue = new Queue<(TreeNode, int)>();
        queue.Enqueue((root, 0));
        while (queue.Count > 0) {
            int count = queue.Count;
            int minIndex = queue.Peek().index;
            int first = 0, last = 0;
            for (int i = 0; i < count; i++) {
                var (node, index) = queue.Dequeue();
                int currIndex = index - minIndex;
                if (i == 0) first = currIndex;
                if (i == count - 1) last = currIndex;
                if (node.left != null) queue.Enqueue((node.left, 2 * currIndex + 1));
                if (node.right != null) queue.Enqueue((node.right, 2 * currIndex + 2));
            }
            maxWidth = Math.Max(maxWidth, last - first + 1);
        }
        return maxWidth;
    }
}

class Program {
    static void Main() {
        TreeNode root = new TreeNode(1,
            new TreeNode(3,
                new TreeNode(5),
                new TreeNode(3)),
            new TreeNode(2,null,
                new TreeNode(9)));
        Solution sol = new Solution();
        Console.WriteLine(sol.WidthOfBinaryTree(root));
    }
}

A 4

B 2

C 5

D 3

💡 Hint

Consider how the indices are assigned to nodes at each level and how width is calculated as last - first + 1.

The maximum width is calculated by tracking the indices of nodes at each level. The widest level here has width 4, including null positions between nodes.

🧠 Conceptual

intermediate

Understanding Indexing in Maximum Width Calculation

Why do we subtract the minimum index of the current level from all node indices before calculating width in the maximum width of binary tree algorithm?

A To ensure the indices correspond to the node values for comparison.

B To prevent integer overflow when indices become very large in deep trees.

C To skip null nodes and only count actual nodes in width calculation.

D To normalize indices so the first node at each level starts at zero, simplifying width calculation.

💡 Hint

Think about how indices grow exponentially and how subtracting the minimum index affects them.

Subtracting the minimum index at each level resets the starting index to zero, which prevents large numbers and simplifies the calculation of width as last - first + 1.

🔧 Debug

advanced

Identify the Bug in Maximum Width Calculation

What error will the following code produce when calculating the maximum width of a binary tree?

DSA C#

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

A The code will cause an integer overflow due to large index values.

B The code will throw a NullReferenceException when accessing node.left or node.right.

C The code will produce incorrect width because indexing starts at 1 but children indices start at 0.

D The code will run correctly and produce the correct maximum width.

💡 Hint

Check how child indices are calculated relative to parent indices and the starting index.

The indexing for children is off by one because the root starts at 1 but children are calculated as 2 * currIndex and 2 * currIndex + 1, which is inconsistent and causes incorrect width calculation.

🚀 Application

advanced

Maximum Width of a Sparse Binary Tree

Given a binary tree where many nodes are missing (null), what will be the maximum width of this tree after running the maximum width algorithm?

DSA C#

TreeNode root = new TreeNode(1,
    null,
    new TreeNode(2,
        null,
        new TreeNode(3,
            null,
            new TreeNode(4))));

A 4

B 2

C 3

D 1

💡 Hint

Consider how the algorithm counts null positions between nodes to calculate width.

The maximum width counts the positions between the leftmost and rightmost nodes at the deepest level, including null gaps, resulting in width 4.

🧠 Conceptual

expert

Why Use a Queue with Indices in Maximum Width Calculation?

Why does the maximum width of binary tree algorithm use a queue that stores pairs of (node, index) instead of just nodes?

A To store the depth level of each node for level order traversal.

B To keep track of the horizontal position of each node to calculate width including gaps caused by null nodes.

C To optimize memory usage by storing indices instead of nodes.

D To sort nodes by their values at each level.

💡 Hint

Think about how the algorithm measures width including empty spaces.

Storing indices allows the algorithm to know the exact horizontal position of nodes, so it can calculate the width including gaps caused by missing nodes.

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