Maximum Width of Binary Tree in DSA Java - Build from Scratch

Maximum Width of Binary Tree

📖 Scenario: You are working with a binary tree data structure. Each node has a value and may have left and right child nodes. You want to find the maximum width of this tree. The width of a level is the number of nodes between the leftmost and rightmost non-null nodes at that level, counting null nodes in between.This is useful in understanding how wide the tree grows at its broadest point.

🎯 Goal: Build a Java program that creates a binary tree, sets up a helper variable for tracking, calculates the maximum width of the tree using level order traversal, and prints the result.

📋 What You'll Learn

Create a binary tree with the exact structure given

Use a queue to traverse the tree level by level

Calculate the maximum width considering null nodes between end nodes

Print the maximum width as an integer

💡 Why This Matters

🌍 Real World

Binary trees are used in many applications like organizing data, searching, and representing hierarchical structures. Knowing the maximum width helps in resource allocation and optimization.

💼 Career

Understanding tree traversal and width calculation is important for software engineers working with data structures, algorithms, and system design.

1

Create the Binary Tree

Create a class called TreeNode with an integer val, and two TreeNode references called left and right. Then create the exact binary tree below by creating TreeNode objects and linking them:

Root node value: 1
Root left child: 3
Root right child: 2
Node 3 left child: 5
Node 3 right child: 3
Node 2 right child: 9

DSA Java

// Define TreeNode class and create the binary tree as described
// Your code here

Hint

Define the TreeNode class first, then create the root and link children exactly as described.

2

Set Up a Queue for Level Order Traversal

Inside the main method, create a Queue of TreeNode called queue using LinkedList. Add the root node to this queue.

DSA Java

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

import java.util.Queue;
import java.util.LinkedList;

public class Main {
    public 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 and add root
        // Your code here
    }
}

Hint

Use Queue queue = new LinkedList<>(); and then queue.add(root);.

3

Calculate Maximum Width of the Binary Tree

Inside the main method, after creating the queue, write code to calculate the maximum width of the binary tree. Use a variable maxWidth initialized to 0. Use a while loop to process nodes level by level. For each level, get the size of the queue as levelSize. Update maxWidth if levelSize is greater. Then, for each node in the level, remove it from the queue and add its left and right children if they are not null.

DSA Java

import java.util.Queue;
import java.util.LinkedList;

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

public class Main {
    public 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 LinkedList();
        queue.add(root);

        // Calculate maxWidth
        // Your code here
    }
}

Hint

Use a while loop to process each level. Update maxWidth with the size of the current level. Use a for loop to process all nodes at the current level.

4

Print the Maximum Width

After the loop, print the value of maxWidth using System.out.println(maxWidth);.

DSA Java

import java.util.Queue;
import java.util.LinkedList;

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

public class Main {
    public 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 LinkedList();
        queue.add(root);

        int maxWidth = 0;
        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            if (levelSize > maxWidth) {
                maxWidth = levelSize;
            }
            for (int i = 0; i < levelSize; i++) {
                TreeNode current = queue.poll();
                if (current.left != null) {
                    queue.add(current.left);
                }
                if (current.right != null) {
                    queue.add(current.right);
                }
            }
        }

        // Print maxWidth
        // Your code here
    }
}

Hint

Use System.out.println(maxWidth); to print the maximum width.

Practice

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

easy

A. The largest number of nodes present at any single level of 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 sum of values of all nodes at the widest level

Solution

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

   The width is the count of nodes at a particular level in the tree.

2. Step 2: Identify maximum width

   The maximum width is the largest such count among all levels.

3. Final Answer:

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

4. Quick Check:

   Maximum width = max nodes at any level [OK]

Hint: Width means count of nodes at one level, find max [OK]

Common Mistakes:

• Confusing width with tree height
• Thinking width is sum of node values
• Counting total nodes instead of per level

2. Which Java data structure is most suitable to track nodes level by level when finding maximum width of a binary tree?

easy

A. Stack

B. HashMap

C. Queue

D. ArrayList

Solution

1. Step 1: Identify traversal method for level order

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

2. Step 2: Choose data structure

   A queue allows nodes to be added and removed in FIFO order, perfect for level traversal.

3. Final Answer:

   Queue -> Option C

4. Quick Check:

   Level order traversal uses queue [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 HashMap which doesn't preserve order
• Using ArrayList without queue behavior

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

class TreeNode {
  int val;
  TreeNode left, right;
  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);

// Maximum width calculation
int maxWidth = 0;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i < size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}
System.out.println(maxWidth);

medium

A. 1

B. 2

C. 3

D. 4

Solution

1. Step 1: Analyze tree levels and node counts

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

2. Step 2: Determine maximum width

   The maximum number of nodes at any level is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at level 2 [OK]

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

Common Mistakes:

• Counting total nodes instead of per level
• Assuming level 3 has 3 nodes incorrectly
• Ignoring null children in width calculation

4. Identify the bug in this Java code snippet that attempts to find the maximum width of a binary tree:

Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int maxWidth = 0;
while (!queue.isEmpty()) {
  int size = queue.size();
  maxWidth = Math.max(maxWidth, size);
  for (int i = 0; i <= size; i++) {
    TreeNode node = queue.poll();
    if (node.left != null) queue.add(node.left);
    if (node.right != null) queue.add(node.right);
  }
}

medium

A. The loop condition should be i < size, not i <= size

B. The queue should be a Stack instead

C. maxWidth should be updated after the for loop

D. The root node is never added to the queue

Solution

1. Step 1: Check the for loop iteration count

   The loop runs from i = 0 to i <= size, which means it runs size+1 times, causing an extra poll.

2. Step 2: Correct the loop condition

   It should run exactly size times, so condition must be i < size.

3. Final Answer:

   The loop condition should be i < size, not i <= size -> Option A

4. Quick Check:

   Loop must run size times exactly [OK]

Hint: Use i < size for loops over queue size [OK]

Common Mistakes:

• Using <= instead of < in for loop
• Replacing queue with stack incorrectly
• Updating maxWidth at wrong place

5. Given a binary tree where some nodes are missing children, how can you modify the maximum width calculation to include null positions between nodes, so the width counts the distance between the leftmost and rightmost non-null nodes at each level? Choose the best approach.

hard

A. Calculate width by summing values of nodes at each level

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

C. Use a stack to store nodes and count them

D. Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1

Solution

1. Step 1: Understand the problem with missing nodes

   Simple counting misses gaps caused by null children, so width is underestimated.

2. Step 2: Use indexing to simulate complete tree positions

   Assign indices to nodes as in a complete binary tree (root=0, left=2*index, right=2*index+1).

3. Step 3: Calculate width per level using min and max indices

   Width = max index - min index + 1, capturing gaps between nodes.

4. Final Answer:

   Assign an index to each node as if the tree was a complete binary tree, track min and max indices per level, width = max - min + 1 -> Option D

5. Quick Check:

   Indexing nodes captures gaps for accurate width [OK]

Hint: Use node indices to count gaps for true width [OK]

Common Mistakes:

• Ignoring null gaps between nodes
• Counting only non-null nodes without positions
• Using stack instead of queue for level traversal