Maximum Width of Binary Tree in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the "maximum width" of a binary tree mean?

The maximum width is the largest (max index - min index + 1) present at any single level (depth) of the binary tree.

intermediate

Why do we assign indices to nodes when calculating the maximum width of a binary tree?

Assigning indices helps track the position of nodes as if the tree was a complete binary tree, allowing us to calculate the width by subtracting the minimum index from the maximum index at each level.

beginner

In the maximum width calculation, how is the width of a level computed using node indices?

Width = (maximum index at that level) - (minimum index at that level) + 1

beginner

What data structure is commonly used to traverse the binary tree level by level for maximum width calculation?

A queue is used to perform a level order traversal (breadth-first search) to process nodes level by level.

intermediate

What is the time complexity of finding the maximum width of a binary tree using level order traversal?

The time complexity is O(n), where n is the number of nodes, because each node is visited once.

What does the maximum width of a binary tree represent?

A The largest (max index - min index + 1) at any level

B The height of the tree

C The number of nodes in the longest path

D The sum of all node values

Maximum width is the largest (max index - min index + 1) at any single level of the tree.

Which traversal method is best suited to calculate the maximum width of a binary tree?

A Inorder traversal

B Level order traversal

C Postorder traversal

D Preorder traversal

Level order traversal visits nodes level by level, which is needed to measure width at each level.

How do we calculate the width of a level using node indices?

A max index - min index + 1

B max index - min index

C max index + min index

D min index - max index + 1

Width is calculated as (max index - min index + 1) to count all nodes between those indices.

Why do we assign indices to nodes during traversal?

A To store node values

B To count total nodes

C To track node positions as if in a complete binary tree

D To sort nodes

Indices help track positions to calculate width correctly, even if some nodes are missing.

What is the space complexity of the maximum width calculation using a queue?

A O(n^2)

B O(log n)

C O(1)

D O(n)

The queue can hold up to all nodes at the widest level, which can be O(n) in the worst case.

Explain how to find the maximum width of a binary tree step-by-step.

Think about visiting nodes level by level and tracking their positions.

Why is it important to assign indices to nodes when calculating maximum width, especially for incomplete trees?

Consider how missing nodes affect counting nodes at a level.

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, not height or sum [OK]

Common Mistakes:

• Confusing width with height of the tree
• Thinking width is total nodes in the tree
• Assuming width is sum of node values

2. Which TypeScript data structure is best suited to track nodes level by level when finding maximum width of a binary tree?

easy

A. Queue

B. Stack

C. Set

D. Map

Solution

1. Step 1: Identify traversal method for levels

   Level order traversal visits nodes level by level, which uses a queue.

2. Step 2: Choose data structure for level order

   A queue allows FIFO order, perfect for processing nodes in each level sequentially.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   Level order traversal uses queue [OK]

Hint: Use queue for level-by-level traversal [OK]

Common Mistakes:

• Using stack which is LIFO, not suitable for level order
• Using set which doesn't maintain order
• Using map which is key-value, not for traversal order

3. What will be the output of the following TypeScript code snippet that calculates maximum width of a binary tree?

class TreeNode {
  val: number;
  left: TreeNode | null;
  right: TreeNode | null;
  constructor(val: number) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

const 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);

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

console.log(maxWidth(root));

medium

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze tree structure and levels

   Level 1: Node 1 (width 1) Level 2: Nodes 2, 3 (width 2) Level 3: Nodes 4, 5 (width 2)

2. Step 2: Check code logic for max width

   Code tracks queue length per level and updates maxWidth. Max width found is 2 at levels 2 and 3.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at widest level [OK]

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

Common Mistakes:

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

4. The following TypeScript function aims to find the maximum width of a binary tree but has a bug. What is the bug?

function maxWidth(root: TreeNode | null): number {
  if (!root) return 0;
  const queue: Array<TreeNode> = [root];
  let maxWidth = 0;
  while (queue.length > 0) {
    const levelSize = queue.length;
    maxWidth = Math.max(maxWidth, levelSize);
    for (let i = 0; i <= levelSize; i++) {
      const node = queue.shift()!;
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

medium

A. The maxWidth should be updated after the for loop

B. The queue should be a stack for correct traversal

C. The for loop condition should be i < levelSize, not i <= levelSize

D. The function should return queue.length instead of maxWidth

Solution

1. Step 1: Examine the for loop condition

   The loop runs from i = 0 to i <= levelSize, which means it runs levelSize + 1 times.

2. Step 2: Identify impact of off-by-one error

   Calling queue.shift() one extra time causes undefined or error because queue is empty after levelSize removals.

3. Final Answer:

   The for loop condition should be i < levelSize, not i <= levelSize -> Option C

4. Quick Check:

   Loop runs exactly levelSize times [OK]

Hint: Use i < levelSize for loops over fixed-size levels [OK]

Common Mistakes:

• Using <= instead of < in loops causing extra iteration
• Confusing queue with stack for level order
• Updating maxWidth inside loop incorrectly

5. Given a binary tree where some nodes are missing (null), how can you modify the maximum width calculation to include the '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 to solve this problem in TypeScript.

hard

A. Count only non-null nodes per level ignoring positions

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

C. Use a stack instead of a queue to track nodes

D. Assign an index to each node as if the tree was a complete binary tree, then calculate width as rightmost index - leftmost index + 1 per level

Solution

1. Step 1: Understand the problem with missing nodes

   Simply counting nodes misses gaps caused by nulls, so width must consider positions.

2. Step 2: Use indexing like a complete binary tree

   Assign indices to nodes: root = 0, left child = 2*index, right child = 2*index + 1. Track min and max indices per level to find width including gaps.

3. Final Answer:

   Assign an index to each node as if the tree was a complete binary tree, then calculate width as rightmost index - leftmost index + 1 per level -> Option D

4. Quick Check:

   Index nodes to include null gaps [OK]

Hint: Use complete tree indexing to count gaps [OK]

Common Mistakes:

• Ignoring null gaps and counting only nodes
• Using stack which breaks level order
• Summing node values instead of counting width