Tree Traversal Level Order BFS in DSA Rust - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: Imagine you have a family tree and you want to visit each generation one by one, starting from the oldest ancestor down to the youngest children.

🎯 Goal: You will build a simple binary tree and write code to visit its nodes level by level using Breadth-First Search (BFS).

📋 What You'll Learn

Create a binary tree with specific nodes

Use a queue to help visit nodes level by level

Print the values of nodes in level order

💡 Why This Matters

🌍 Real World

Level order traversal is useful in scenarios like finding the shortest path in a network, scheduling tasks level by level, or processing hierarchical data generation-wise.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working on algorithms, data processing, and system design.

1

Create the binary tree structure and nodes

Define a struct called TreeNode with fields val of type i32, left and right as Option>. Then create a variable called root representing the root node with value 1, left child with value 2, and right child with value 3. The left child of 2 should be 4 and right child 5. The right child of 3 should be 6. All other children are None.

DSA Rust

// Define TreeNode struct and create root node with children
// Your code here

Hint

Use Option> for left and right children to allow empty branches.

2

Set up a queue to help with level order traversal

Inside main, create a mutable vector called queue of type Vec<&TreeNode> and push a reference to root into it.

DSA Rust

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

fn main() {
    let root = TreeNode {
        val: 1,
        left: Some(Box::new(TreeNode {
            val: 2,
            left: Some(Box::new(TreeNode { val: 4, left: None, right: None })),
            right: Some(Box::new(TreeNode { val: 5, left: None, right: None })),
        })),
        right: Some(Box::new(TreeNode {
            val: 3,
            left: None,
            right: Some(Box::new(TreeNode { val: 6, left: None, right: None })),
        })),
    };
    
    // Create a queue and add root reference
    // Your code here
}

Hint

Use Vec as a queue and push the root node reference to start.

3

Implement the level order traversal loop

Write a while loop that runs while queue is not empty. Inside the loop, remove the first element from queue using remove(0) and store it in current. Then, if current.left is Some, push a reference to the left child into queue. Similarly, if current.right is Some, push a reference to the right child into queue. Print the value of current.val inside the loop.

DSA Rust

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

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

    let mut queue: Vec = Vec::new();
    queue.push(&root);

    // Write while loop for level order traversal
    // Your code here
}

Hint

Use remove(0) to get the first element from the queue and if let Some(ref child) to check children.

4

Print the level order traversal result

Run the program to print the values of the tree nodes in level order. The output should be the values separated by new lines.

DSA Rust

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

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

    let mut queue: Vec = Vec::new();
    queue.push(&root);

    while !queue.is_empty() {
        let current = queue.remove(0);
        println!("{}", current.val);
        if let Some(ref left_child) = current.left {
            queue.push(left_child);
        }
        if let Some(ref right_child) = current.right {
            queue.push(right_child);
        }
    }

    // Output is printed above

Hint

Run the program and check the printed values match the expected level order.

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