Tree Traversal Level Order BFS in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this level order traversal?

Given the binary tree below, what is the printed output of the level order traversal (BFS)?

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

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

fn main() {
    let root = Some(Box::new(Node {
        val: 1,
        left: Some(Box::new(Node {
            val: 2,
            left: None,
            right: None,
        })),
        right: Some(Box::new(Node {
            val: 3,
            left: Some(Box::new(Node {
                val: 4,
                left: None,
                right: None,
            })),
            right: None,
        })),
    }));
    let output = level_order(&root);
    println!("{:?}", output);
}

A [1, 3, 4, 2]

B [1, 3, 2, 4]

C [1, 2, 4, 3]

D [1, 2, 3, 4]

💡 Hint

Remember, level order traversal visits nodes level by level from left to right.

The traversal visits root first (1), then its children left to right (2, 3), then the next level nodes (4). So the output is [1, 2, 3, 4].

🧠 Conceptual

intermediate

How many nodes are visited in level order traversal?

Given a binary tree with 7 nodes, how many nodes will the level order traversal visit?

A 7

B 6

C 8

D Depends on the tree structure

💡 Hint

Level order traversal visits every node exactly once.

Level order traversal visits every node in the tree exactly once, so for 7 nodes, it visits all 7.

🔧 Debug

advanced

What error does this code raise?

What error will this Rust code produce when performing level order traversal?

DSA Rust

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

A Error: cannot move out of borrowed content

B Error: use of moved value 'queue'

C Error: mismatched types, expected Option<Box<Node>>

D No error, runs correctly

💡 Hint

Check how you access left and right children inside the loop.

The code tries to move out of a borrowed reference when accessing current.left and current.right, which is not allowed in Rust.

🚀 Application

advanced

Which option prints nodes level by level with each level on a new line?

Given a binary tree, which Rust code snippet correctly prints nodes level by level, each level on its own line?

DSA Rust

struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

// Assume root is defined

A

fn print_levels(root: &Option<Box<Node>>) {
    let mut queue = std::collections::VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while let Some(current) = queue.pop_front() {
        print!("{} ", current.val);
        if let Some(left) = &current.left {
            queue.push_back(left);
        }
        if let Some(right) = &current.right {
            queue.push_back(right);
        }
        println!();
    }
}

B

fn print_levels(root: &Option<Box<Node>>) {
    let mut queue = std::collections::VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let level_size = queue.len();
        for _ in 0..level_size {
            let current = queue.pop_front().unwrap();
            print!("{} ", current.val);
        }
        println!();
    }
}

C

fn print_levels(root: &Option<Box<Node>>) {
    let mut queue = std::collections::VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let level_size = queue.len();
        for _ in 0..level_size {
            let current = queue.pop_front().unwrap();
            print!("{} ", current.val);
            if let Some(left) = &current.left {
                queue.push_back(left);
            }
            if let Some(right) = &current.right {
                queue.push_back(right);
            }
        }
        println!();
    }
}

D

fn print_levels(root: &Option<Box<Node>>) {
    let mut queue = std::collections::VecDeque::new();
    if let Some(node) = root {
        queue.push_back(node);
    }
    while !queue.is_empty() {
        let current = queue.pop_front().unwrap();
        print!("{} ", current.val);
        if let Some(left) = &current.left {
            queue.push_back(left);
        }
        if let Some(right) = &current.right {
            queue.push_back(right);
        }
        println!();
    }
}

💡 Hint

Use the queue length before processing each level to separate levels.

Option C correctly uses the queue length to process nodes level by level and prints a newline after each level. Others either print newline after every node or miss enqueuing children properly.

🧠 Conceptual

expert

What is the time complexity of level order traversal on a binary tree with n nodes?

Choose the correct time complexity for performing a level order traversal (BFS) on a binary tree with n nodes.

A O(log n)

B O(n)

C O(n log n)

D O(n^2)

💡 Hint

Each node is visited exactly once during traversal.

Level order traversal visits each node once and processes its children, so the time complexity is linear in the number of nodes, O(n).

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