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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Maximum Width Calculation for a Simple Tree

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

DSA Rust

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn width_of_binary_tree(root: Option<Box<TreeNode>>) -> usize {
    if root.is_none() {
        return 0;
    }
    let mut max_width = 0;
    let mut queue = VecDeque::new();
    queue.push_back((root, 0usize));

    while !queue.is_empty() {
        let level_length = queue.len();
        let first_index = queue.front().unwrap().1;
        let mut last_index = first_index;

        for _ in 0..level_length {
            let (node_opt, index) = queue.pop_front().unwrap();
            if let Some(node) = node_opt {
                if node.left.is_some() {
                    queue.push_back((node.left.clone(), 2 * index));
                }
                if node.right.is_some() {
                    queue.push_back((node.right.clone(), 2 * index + 1));
                }
            }
            last_index = index;
        }
        max_width = max_width.max(last_index - first_index + 1);
    }
    max_width
}

fn main() {
    let mut root = Box::new(TreeNode::new(1));
    root.left = Some(Box::new(TreeNode::new(2)));
    root.right = Some(Box::new(TreeNode::new(3)));
    root.left.as_mut().unwrap().left = Some(Box::new(TreeNode::new(4)));
    root.right.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));

    let width = width_of_binary_tree(Some(root));
    println!("{}", width);
}

A 2

B 3

C 4

D 5

💡 Hint

Think about the positions of nodes at the widest level and how indices are assigned.

The maximum width is calculated by tracking the indices of nodes at each level. The widest level here is the last one with nodes 4 and 5, which are at positions 0 and 3 respectively, so width = 3 - 0 + 1 = 4.

🧠 Conceptual

intermediate

Understanding Indexing in Maximum Width Calculation

In the maximum width calculation of a binary tree, why do we assign indices to nodes as if the tree was a complete binary tree?

A To keep track of the horizontal position of nodes and calculate width correctly even with missing nodes

B To count the total number of nodes in the tree

C To find the height of the tree

D To sort the nodes by their values

💡 Hint

Think about how missing nodes affect the width measurement.

Assigning indices as if the tree was complete helps us measure the horizontal distance between nodes, including gaps caused by missing nodes, so we get the true maximum width.

🔧 Debug

advanced

Identify the Error in Maximum Width Calculation Code

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

DSA Rust

fn width_of_binary_tree(root: Option<Box<TreeNode>>) -> usize {
    if root.is_none() {
        return 0;
    }
    let mut max_width = 0;
    let mut queue = VecDeque::new();
    queue.push_back((root, 0usize));

    while !queue.is_empty() {
        let level_length = queue.len();
        let first_index = queue.front().unwrap().1;
        let mut last_index = first_index;

        for _ in 0..level_length {
            let (node_opt, index) = queue.pop_front().unwrap();
            if let Some(node) = node_opt {
                if node.left.is_some() {
                    queue.push_back((node.left.clone(), 2 * index + 1));
                }
                if node.right.is_some() {
                    queue.push_back((node.right.clone(), 2 * index + 2));
                }
            }
            last_index = index;
        }
        max_width = max_width.max(last_index - first_index + 1);
    }
    max_width
}

A The code runs correctly and returns the maximum width

B The code calculates incorrect width because left and right child indices are swapped

C The code will not compile due to missing imports

D The code will panic due to unwrap on an empty queue

💡 Hint

Check how indices for left and right children are assigned.

The indices for left and right children should be 2 * index and 2 * index + 1 respectively. Swapping them causes incorrect width calculation.

🚀 Application

advanced

Maximum Width of a Sparse Binary Tree

Given a binary tree where many nodes are missing, which approach correctly calculates the maximum width?

A Use level order traversal with indices assigned as if the tree was complete, tracking min and max indices per level

B Count nodes at each level ignoring missing nodes

C Calculate width as the difference between the leftmost and rightmost node values at each level

D Use depth-first search to count nodes and multiply by level number

💡 Hint

Consider how missing nodes affect width measurement.

Assigning indices simulating a complete tree allows capturing gaps caused by missing nodes, giving the true maximum width.

❓ Predict Output

expert

Output of Maximum Width Calculation on a Complex Tree

What is the output of the following Rust code that calculates the maximum width of a complex binary tree?

DSA Rust

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, left: None, right: None }
    }
}

fn width_of_binary_tree(root: Option<Box<TreeNode>>) -> usize {
    if root.is_none() {
        return 0;
    }
    let mut max_width = 0;
    let mut queue = VecDeque::new();
    queue.push_back((root, 0usize));

    while !queue.is_empty() {
        let level_length = queue.len();
        let first_index = queue.front().unwrap().1;
        let mut last_index = first_index;

        for _ in 0..level_length {
            let (node_opt, index) = queue.pop_front().unwrap();
            if let Some(node) = node_opt {
                if node.left.is_some() {
                    queue.push_back((node.left.clone(), 2 * index));
                }
                if node.right.is_some() {
                    queue.push_back((node.right.clone(), 2 * index + 1));
                }
            }
            last_index = index;
        }
        max_width = max_width.max(last_index - first_index + 1);
    }
    max_width
}

fn main() {
    let mut root = Box::new(TreeNode::new(1));
    root.left = Some(Box::new(TreeNode::new(2)));
    root.right = Some(Box::new(TreeNode::new(3)));
    root.left.as_mut().unwrap().right = Some(Box::new(TreeNode::new(4)));
    root.right.as_mut().unwrap().right = Some(Box::new(TreeNode::new(5)));
    root.left.as_mut().unwrap().right.as_mut().unwrap().left = Some(Box::new(TreeNode::new(6)));

    let width = width_of_binary_tree(Some(root));
    println!("{}", width);
}

A 4

B 6

C 3

D 5

💡 Hint

Trace the indices assigned to nodes at each level carefully.

The widest level is the last one with nodes at indices 4 and 8, so width = 8 - 4 + 1 = 5.

Practice

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

easy

A. The total number of nodes in the tree

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

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 definition of width in a binary tree

   The width of a binary tree at a level is the count of nodes present at that level.

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 C

4. Quick Check:

   Width = max nodes at any level [OK]

Hint: Width means count of nodes at widest level [OK]

Common Mistakes:

• Confusing width with tree height
• Thinking width is sum of node values
• Mixing width with total nodes count

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

easy

A. VecDeque (double-ended queue)

B. Vec (vector)

C. HashMap

D. BTreeSet

Solution

1. Step 1: Identify the need for level order traversal

   To find maximum width, we visit nodes level by level, which is a breadth-first search (BFS).

2. Step 2: Choose data structure for BFS

   BFS uses a queue to process nodes in FIFO order. Rust's VecDeque supports efficient push/pop from both ends.

3. Final Answer:

   VecDeque (double-ended queue) -> Option A

4. Quick Check:

   Use queue (VecDeque) for BFS traversal [OK]

Hint: Use VecDeque for efficient queue operations in BFS [OK]

Common Mistakes:

• Using Vec which is inefficient for queue operations
• Using HashMap which is unordered
• Using BTreeSet which is for sorted unique elements

3. Given the following Rust code snippet for maximum width calculation, what is the printed output?

struct TreeNode {
    val: i32,
    left: Option,
    right: Option,
}

fn max_width(root: Option) -> usize {
    use std::collections::VecDeque;
    if root.is_none() { return 0; }
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());
    let mut max_width = 0;
    while !queue.is_empty() {
        let level_size = queue.len();
        max_width = max_width.max(level_size);
        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            if let Some(left) = node.left {
                queue.push_back(left);
            }
            if let Some(right) = node.right {
                queue.push_back(right);
            }
        }
    }
    max_width
}

fn main() {
    let root = Some(Box::new(TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode { val: 2, left: None, right: None })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: None,
        })),
    }));
    println!("{}", max_width(root));
}

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Analyze the tree structure

   Level 1: Node 1 (1 node) Level 2: Nodes 2 and 3 (2 nodes) Level 3: Node 4 (1 node)

2. Step 2: Calculate maximum width

   Widths per level: 1, 2, 1 Maximum width is 2.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Max width = 2 nodes at level 2 [OK]

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

Common Mistakes:

• Counting total nodes instead of per level
• Ignoring empty children in width calculation
• Confusing node values with count

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

fn max_width(root: Option) -> usize {
    use std::collections::VecDeque;
    if root.is_none() { return 0; }
    let mut queue = VecDeque::new();
    queue.push_back(root.unwrap());
    let mut max_width = 0;
    while !queue.is_empty() {
        let level_size = queue.len();
        max_width = max_width.max(level_size);
        for _ in 0..level_size {
            let node = queue.pop_front().unwrap();
            if node.left.is_some() {
                queue.push_back(node.left.unwrap());
            }
            if node.right.is_some() {
                queue.push_back(node.right.unwrap());
            }
        }
    }
    max_width
}

medium

A. Not handling empty tree case

B. Using VecDeque instead of Vec causes performance issues

C. Not updating max_width inside the loop

D. Calling unwrap() on Option without checking causes panic

Solution

1. Step 1: Identify unsafe unwrap calls

   Calling unwrap() on node.left or node.right without safely extracting causes panic if None.

2. Step 2: Correct approach

   Use if let Some(left) = node.left { queue.push_back(left); } to safely handle Options.

3. Final Answer:

   Calling unwrap() on Option without checking causes panic -> Option D

4. Quick Check:

   Unsafe unwrap causes runtime panic [OK]

Hint: Use if let to safely unwrap Options [OK]

Common Mistakes:

• Using unwrap() directly on Option fields
• Ignoring empty tree check (though present here)
• Confusing VecDeque with Vec performance

5. You want to find the maximum width of a binary tree where some levels have missing nodes between others (e.g., a sparse tree). Which approach correctly calculates the maximum width including gaps between nodes? A common method is to assign position indices to nodes as if the tree was a complete binary tree. Which Rust code snippet correctly updates the maximum width using position indices during level order traversal?

use std::collections::VecDeque;

fn max_width_with_positions(root: Option) -> usize {
    if root.is_none() { return 0; }
    let mut max_width = 0;
    let mut queue = VecDeque::new();
    queue.push_back((root.unwrap(), 0usize));
    while !queue.is_empty() {
        let level_length = queue.len();
        let first_index = queue.front().unwrap().1;
        let last_index;
        for i in 0..level_length {
            let (node, idx) = queue.pop_front().unwrap();
            let idx = idx - first_index; // normalize to prevent overflow
            if node.left.is_some() {
                queue.push_back((node.left.unwrap(), 2 * idx + 1));
            }
            if node.right.is_some() {
                queue.push_back((node.right.unwrap(), 2 * idx + 2));
            }
            if i == level_length - 1 {
                last_index = idx;
            }
        }
        max_width = max_width.max(last_index + 1);
    }
    max_width
}

hard

A. Normalize indices by subtracting first index at each level to avoid overflow

B. Use raw indices without normalization to get exact positions

C. Ignore indices and count nodes only for width

D. Use depth instead of indices for width calculation

Solution

1. Step 1: Understand position indexing

   Assigning indices as if complete binary tree helps measure width including gaps.

2. Step 2: Normalize indices to prevent overflow

   Subtracting first index at each level keeps indices small and prevents usize overflow.

3. Step 3: Calculate width as last_index - first_index + 1

   Using normalized indices, width = last_index + 1 at each level.

4. Final Answer:

   Normalize indices by subtracting first index at each level to avoid overflow -> Option A

5. Quick Check:

   Index normalization prevents overflow and calculates width correctly [OK]

Hint: Subtract first index each level to keep indices small [OK]

Common Mistakes:

• Not normalizing indices causing overflow
• Ignoring gaps by counting nodes only
• Using depth instead of position indices