Maximum Width of Binary Tree in DSA C# - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: Imagine you are working with a family tree app that shows generations of family members. You want to find out the widest generation in the tree, meaning the generation with the most members including empty spots between them.

🎯 Goal: Build a program that calculates the maximum width of a binary tree. The width is the number of nodes between the leftmost and rightmost non-null nodes at any level, counting nulls in between.

📋 What You'll Learn

Create a binary tree using the TreeNode class with exact nodes and values.

Use a queue to traverse the tree level by level.

Calculate the width of each level considering null positions.

Print the maximum width found.

💡 Why This Matters

🌍 Real World

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

💼 Career

This concept is useful for software engineers working with tree data structures, optimizing database queries, or designing efficient algorithms for hierarchical data.

1

Create the Binary Tree

Create the binary tree using the TreeNode class with this exact structure and values:
root node with value 1,
left child with value 3,
right child with value 2,
left child of node 3 with value 5,
right child of node 3 with value 3,
right child of node 2 with value 9.

DSA C#

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;
    }
}

class Program
{
    static void Main(string[] args)
    {
        // Create the binary tree nodes as described
        // Your code here
    }
}

Hint

Start by creating the root node with value 1. Then add children exactly as described using root.left and root.right.

2

Set Up a Queue for Level Order Traversal

Add a Queue of tuples called queue to hold pairs of TreeNode and int index. Initialize it with the root node and index 0.

DSA C#

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;
    }
}

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);

        // Create a queue of (TreeNode, int) and enqueue root with index 0
        // Your code here
    }
}

Hint

Use Queue<(TreeNode, int)> and add the root node with index 0 to start level order traversal.

3

Calculate Maximum Width Using Level Order Traversal

Write a while loop that runs while queue.Count > 0. Inside, get the count of nodes in the queue. For each node in the current level, dequeue it, and enqueue its children with calculated indices: left child index = 2 * index, right child index = 2 * index + 1. Track the minimum and maximum indices at each level to calculate the width. Update a variable maxWidth to keep the maximum width found.

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;
    }
}

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);

        Queue queue = new Queue();
        queue.Enqueue((root, 0));

        // Calculate maxWidth using level order traversal
        // Your code here
    }
}

Hint

Use a while loop to process each level. Normalize indices by subtracting the first index of the level. Update maxWidth after each level.

4

Print the Maximum Width

Add a Console.WriteLine statement to print the value of maxWidth.

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;
    }
}

class Program
{
    static void Main(string[] args)
    {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(5);
        root.left.right = new TreeNode(3);
        root.right.right = new TreeNode(9);

        Queue queue = new Queue();
        queue.Enqueue((root, 0));

        int maxWidth = 0;

        while (queue.Count > 0)
        {
            int count = queue.Count;
            int minIndex = queue.Peek().index;
            int first = 0, last = 0;

            for (int i = 0; i  maxWidth)
                maxWidth = width;
        }

        // Print the maximum width
        // Your code here
    }
}

Hint

Use Console.WriteLine(maxWidth); to show the final maximum width.

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