Tree Traversal Level Order BFS in DSA Rust - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a queue for BFS traversal.

DSA Rust

let mut queue = VecDeque::new();
queue.[1](root);

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

Apush_back

Bpop_front

Cpush_front

Dpop_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop methods instead of push to add elements.

Using push_front which adds to the front, not suitable for BFS enqueue.

We use push_back to add the root node at the end of the queue for BFS.

2fill in blank

medium

Complete the code to remove the front node from the queue during BFS.

DSA Rust

while let Some(node) = queue.[1]() {
    // process node
}

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

Apop_front

Bpush_back

Cpop_back

Dpush_front

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop_back which removes from the end, not suitable for BFS.

Using push methods instead of pop.

We use pop_front to remove the node at the front of the queue for BFS traversal.

3fill in blank

hard

Fix the error in adding child nodes to the queue during BFS traversal.

DSA Rust

if let Some(left) = node.left.as_ref() {
    queue.[1](left);
}

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

Apop_front

Bpush_front

Cpop_back

Dpush_back

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop methods which remove elements instead of adding.

Using push_front which adds to the front, breaking BFS order.

We add child nodes to the back of the queue using push_back to maintain BFS order.

4fill in blank

hard

Fill both blanks to correctly collect node values and enqueue children in BFS.

DSA Rust

let mut result = Vec::new();
while let Some(node) = queue.pop_front() {
    result.push(node.[1]);
    if let Some(left) = node.left.as_ref() {
        queue.[2](left);
    }
}

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

Aval

Bpush_back

Cpush_front

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect field name like value.

Using push_front which breaks BFS order.

We access the node's value with val and add children to the queue with push_back.

5fill in blank

hard

Fill all three blanks to complete BFS traversal collecting all node values.

DSA Rust

use std::collections::VecDeque;

fn level_order(root: Option<&Box<TreeNode>>) -> Vec<i32> {
    let mut result = Vec::new();
    if root.is_none() {
        return result;
    }
    let mut queue = VecDeque::new();
    queue.[1](root.unwrap());
    while let Some(node) = queue.pop_front() {
        result.push(node.[2]);
        if let Some(left) = node.left.as_ref() {
            queue.[3](left);
        }
    }
    result
}

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

Apush_back

Bval

Dpop_front

Attempts:

3 left

💡 Hint

Common Mistakes

Using pop_front to add elements instead of removing.

Using wrong field name for node value.

Using push_front which breaks BFS order.

We enqueue the root with push_back, access node value with val, and enqueue children with push_back.

Practice

1. What does the Level Order Traversal (BFS) of a binary tree do?

easy

A. Visits nodes in preorder: root, left, right

B. Visits nodes level by level from top to bottom, left to right

C. Visits nodes in postorder: left, right, root

D. Visits nodes in inorder: left, root, right

Solution

1. Step 1: Understand Level Order Traversal

   Level Order Traversal visits nodes one level at a time, starting from the root and moving downwards.

2. Step 2: Compare with other traversals

   Preorder, inorder, and postorder are depth-first traversals, not level by level.

3. Final Answer:

   Visits nodes level by level from top to bottom, left to right -> Option B

4. Quick Check:

   Level Order = BFS = top to bottom, left to right [OK]

Hint: Level order means visiting nodes level by level [OK]

Common Mistakes:

• Confusing BFS with DFS traversals
• Thinking preorder is level order
• Mixing traversal orders

2. Which Rust code snippet correctly initializes a queue for BFS traversal of a binary tree?

easy

A. let mut queue: VecDeque<&TreeNode> = VecDeque::new();

B. let mut queue: Vec<&TreeNode> = Vec::new();

C. let mut queue: LinkedList<TreeNode> = LinkedList::new();

D. let mut queue: HashMap = HashMap::new();

Solution

1. Step 1: Identify the correct queue type for BFS

   BFS requires a queue with efficient push and pop from front, VecDeque is ideal in Rust.

2. Step 2: Check other options

   Vec is a stack-like structure, LinkedList is less common and less efficient, HashMap is a key-value store, not a queue.

3. Final Answer:

   let mut queue: VecDeque<&TreeNode> = VecDeque::new(); -> Option A

4. Quick Check:

   VecDeque is the queue for BFS in Rust [OK]

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

Common Mistakes:

• Using Vec which is inefficient for queue
• Using HashMap instead of queue
• Confusing LinkedList with VecDeque

3. What is the output of the following Rust code performing level order traversal?

use std::collections::VecDeque;

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

fn level_order(root: Option) -> Vec<i32> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while let Some(node) = queue.pop_front() {
        result.push(node.val);
        if let Some(left) = node.left {
            queue.push_back(left);
        }
        if let Some(right) = node.right {
            queue.push_back(right);
        }
    }
    result
}

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: None, right: None })),
    }));
    let output = level_order(root);
    println!("{:?}", output);
}

medium

A. [1, 2, 3]

B. [1, 3, 2]

C. [2, 1, 3]

D. [3, 2, 1]

Solution

1. Step 1: Trace the queue operations

   Start with root 1 in queue. Pop 1, add 2 and 3 to queue. Result: [1]

2. Step 2: Continue traversal

   Pop 2, no children. Result: [1, 2]. Pop 3, no children. Result: [1, 2, 3]. Queue empty, stop.

3. Final Answer:

   [1, 2, 3] -> Option A

4. Quick Check:

   Level order visits 1 then 2 then 3 [OK]

Hint: Follow queue push/pop order carefully [OK]

Common Mistakes:

• Mixing left and right child order
• Confusing preorder with level order
• Forgetting to push children into queue

4. Identify the bug in this Rust BFS traversal code snippet:

while let Some(node) = queue.pop_front() {
    result.push(node.val);
    queue.push_back(node.left.unwrap());
    queue.push_back(node.right.unwrap());
}

medium

A. Using pop_front() instead of pop_back()

B. Not pushing root node into queue before loop

C. Result vector is not initialized

D. Using unwrap() directly causes panic if Option is None

Solution

1. Step 1: Analyze unwrap() usage

   Calling unwrap() on Option without safe check can panic if None.

2. Step 2: Check safer alternative

   Better to use if let Some(left) = node.left to safely extract without panic.

3. Final Answer:

   Using unwrap() directly causes panic if Option is None -> Option D

4. Quick Check:

   unwrap() on None panics, use if let Some() [OK]

Hint: Avoid unwrap() on Option without safe check [OK]

Common Mistakes:

• Assuming unwrap() is always safe
• Ignoring initialization of queue
• Confusing pop_front and pop_back

5. Given a binary tree, how would you modify the level order BFS traversal in Rust to return a vector of vectors, where each inner vector contains the node values at that level?

hard

A. Traverse the tree recursively and collect nodes in a single vector, then split by level afterwards

B. Use a stack instead of queue to reverse the order of nodes per level

C. Use a queue and track the number of nodes at each level, collecting values into inner vectors before moving to next level

D. Store all nodes in a HashMap with level as key, then flatten values into a single vector

Solution

1. Step 1: Understand level grouping in BFS

   Track how many nodes are in the current level by queue length before processing that level.

2. Step 2: Collect nodes per level

   For each level, pop exactly that many nodes, collect their values into a vector, then push their children for next level.

3. Final Answer:

   Use a queue and track the number of nodes at each level, collecting values into inner vectors before moving to next level -> Option C

4. Quick Check:

   Level order + count nodes per level = vector of vectors [OK]

Hint: Count nodes per level in queue to group values [OK]

Common Mistakes:

• Using recursion instead of BFS for level grouping
• Using stack which reverses order
• Trying to split flat vector after traversal