Maximum Width of Binary Tree in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the root node and its index.

DSA Javascript

let queue = [[root, [1]]];

Drag options to blanks, or click blank then click option'

A0

Bnull

C-1

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting index at 1 instead of 0

Using null as index

Using negative index

The root node is assigned index 0 to start the level indexing from zero.

2fill in blank

medium

Complete the code to calculate the width of the current level.

DSA Javascript

let width = lastIndex - firstIndex + [1];

Drag options to blanks, or click blank then click option'

A0

B-1

C1

D2

Attempts:

3 left

💡 Hint

Common Mistakes

Not adding 1 to the difference

Subtracting instead of adding

Using zero which undercounts width

Width is calculated as last index minus first index plus one to include both ends.

3fill in blank

hard

Fix the error in the code that adds the left child to the queue with correct index.

DSA Javascript

if (node.left) queue.push([node.left, [1]]);

Drag options to blanks, or click blank then click option'

Aindex * 2

Bindex * 2 + 1

Cindex + 1

Dindex - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using index * 2 + 1 for left child

Using index + 1 which is incorrect for tree indexing

Using negative indices

Left child's index is parent's index times 2 to maintain position in a full binary tree.

4fill in blank

hard

Fill both blanks to add the right child to the queue with correct index and update maxWidth.

DSA Javascript

if (node.right) queue.push([node.right, [1]]);
maxWidth = Math.max(maxWidth, [2]);

Drag options to blanks, or click blank then click option'

Aindex * 2 + 1

Bwidth

ClastIndex - firstIndex + 1

Dindex * 2

Attempts:

3 left

💡 Hint

Common Mistakes

Using index * 2 for right child

Updating maxWidth with index instead of width

Not updating maxWidth at all

Right child's index is parent's index times 2 plus 1; maxWidth updates with current level width.

5fill in blank

hard

Fill all three blanks to complete the function that returns the maximum width of a binary tree.

DSA Javascript

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  let queue = [[root, [1]]];
  while (queue.length) {
    let levelLength = queue.length;
    let firstIndex = queue[0][1];
    let lastIndex = queue[queue.length - 1][1];
    maxWidth = Math.max(maxWidth, lastIndex - firstIndex + [2]);
    for (let i = 0; i < levelLength; i++) {
      let [node, index] = queue.shift();
      index -= firstIndex;
      if (node.left) queue.push([node.left, index * 2 + [3]]);
      if (node.right) queue.push([node.right, index * 2 + 1]);
    }
  }
  return maxWidth;
}

Drag options to blanks, or click blank then click option'

A0

B1

Attempts:

3 left

💡 Hint

Common Mistakes

Starting index at 1

Not adding 1 to width

Using 1 instead of 0 for left child index offset

Start indexing at 0; add 1 to width calculation; left child index is index * 2 + 0.

Practice

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

easy

A. The height of the tree from root to the deepest leaf

B. The total number of nodes in the tree

C. The largest number of nodes present at any single level of the tree

D. The sum of values of all nodes at the widest level

Solution

1. Step 1: Understand the term 'width' in a binary tree

   The width refers to how many nodes exist at the same depth or level in the tree.

2. Step 2: Identify what 'maximum width' means

   It is the largest count of nodes found at any one level across the entire tree.

3. Final Answer:

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

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
• Mixing width with sum of node values

2. Which of the following JavaScript code snippets correctly initializes a queue to help calculate the maximum width of a binary tree?

easy

A. const queue = {};

B. const queue = [];

C. const queue = new Set();

D. const queue = null;

Solution

1. Step 1: Identify the correct data structure for BFS traversal

   To calculate maximum width, we use level order traversal which requires a queue (FIFO).

2. Step 2: Check JavaScript syntax for queue initialization

   An array can be used as a queue with push and shift methods, so const queue = [] is correct.

3. Final Answer:

   const queue = []; -> Option B

4. Quick Check:

   Queue for BFS = array [] [OK]

Hint: Use array [] as queue for BFS in JavaScript [OK]

Common Mistakes:

• Using Set which is unordered
• Using object {} which is not a queue
• Assigning null instead of a data structure

3. Consider the following JavaScript code to find the maximum width of a binary tree. What will be the output?

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

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

function widthOfBinaryTree(root) {
  if (!root) return 0;
  let maxWidth = 0;
  const queue = [[root, 0]]; // node with index
  while (queue.length) {
    const levelLength = queue.length;
    const levelIndices = [];
    for (let i = 0; i < levelLength; i++) {
      const [node, index] = queue.shift();
      levelIndices.push(index);
      if (node.left) queue.push([node.left, 2 * index]);
      if (node.right) queue.push([node.right, 2 * index + 1]);
    }
    maxWidth = Math.max(maxWidth, levelIndices[levelIndices.length - 1] - levelIndices[0] + 1);
  }
  return maxWidth;
}

console.log(widthOfBinaryTree(root));

medium

A. 4

B. 3

C. 2

D. 5

Solution

1. Step 1: Analyze the tree structure and node indices

   Level 0: Node 1 at index 0 (width 1) Level 1: Nodes 2 (index 0), 3 (index 1) width = 2 Level 2: Nodes 4 (0), 5 (1), null, 7 (3) width = 3 - 0 + 1 = 4

2. Step 2: Calculate maximum width from indices

   The widest level is level 2 with width 4, so maxWidth = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   Max width = 4 nodes at level 2 [OK]

Hint: Track node indices to find width = max index - min index + 1 [OK]

Common Mistakes:

• Ignoring null gaps in indexing
• Counting nodes instead of width using indices
• Confusing index calculation for children

4. The following code attempts to compute the maximum width of a binary tree but has a bug. What is the bug?

function maxWidth(root) {
  if (!root) return 0;
  let maxWidth = 0;
  const queue = [root];
  while (queue.length) {
    const levelLength = queue.length;
    maxWidth = Math.max(maxWidth, levelLength);
    for (let i = 0; i < levelLength; i++) {
      const node = queue.shift();
      if (node.left) queue.push(node.left);
      if (node.right) queue.push(node.right);
    }
  }
  return maxWidth;
}

medium

A. It pushes nodes into queue before checking if queue is empty

B. It uses shift() which is not allowed in JavaScript arrays

C. It does not initialize maxWidth to zero

D. It does not consider null nodes between children, so width may be underestimated

Solution

1. Step 1: Understand how width is calculated here

   This code counts nodes at each level but ignores gaps caused by missing nodes (nulls).

2. Step 2: Identify why ignoring nulls causes wrong width

   Width should count positions including nulls between nodes, but this code only counts existing nodes, underestimating width.

3. Final Answer:

   It does not consider null nodes between children, so width may be underestimated -> Option D

4. Quick Check:

   Missing nulls causes wrong width [OK]

Hint: Include nulls in queue to track gaps for correct width [OK]

Common Mistakes:

• Thinking shift() is invalid in JS arrays
• Ignoring null gaps in width calculation
• Misunderstanding queue initialization

5. You want to find the maximum width of a binary tree but the tree can be very deep and sparse. Which approach below best handles this efficiently in JavaScript?

hard

A. Use level order traversal with node indices to track positions and calculate width

B. Use depth-first traversal and count nodes at each depth without indices

C. Use recursion to count total nodes and divide by height

D. Use a stack to store nodes and calculate width by node values

Solution

1. Step 1: Consider the problem of deep and sparse trees

   Deep sparse trees have missing nodes causing gaps; simple node counts per level won't work.

2. Step 2: Choose method that tracks node positions

   Level order traversal with indices tracks exact positions, including gaps, allowing correct width calculation.

3. Step 3: Evaluate other options

   DFS without indices can't track gaps; recursion counting nodes/height is inaccurate; stack with node values doesn't help width.

4. Final Answer:

   Use level order traversal with node indices to track positions and calculate width -> Option A

5. Quick Check:

   Index tracking + BFS = correct max width [OK]

Hint: Track indices in BFS to handle sparse trees efficiently [OK]

Common Mistakes:

• Using DFS without position tracking
• Assuming total nodes/height gives width
• Using node values instead of positions