Tree Traversal Level Order BFS in DSA Rust

Mental Model

Visit tree nodes level by level from top to bottom, left to right.

Analogy: Imagine a group of friends standing in rows. You greet all friends in the first row, then move to the second row, and so on.

      1
     / \
    2   3
   / \   \
  4   5   6

Queue: []
Start at root node 1

Dry Run Walkthrough

Input: Tree: 1 with children 2 and 3; 2 has children 4 and 5; 3 has child 6

Goal: Print nodes level by level: 1, then 2 and 3, then 4, 5, and 6

Step 1: Add root node 1 to queue

Queue: [1]

Why: Start traversal from the root

Step 2: Remove 1 from queue and visit it; add its children 2 and 3 to queue

Visited: 1
Queue: [2 -> 3]

Why: Visit current level node and prepare next level nodes

Step 3: Remove 2 from queue and visit it; add its children 4 and 5 to queue

Visited: 1, 2
Queue: [3 -> 4 -> 5]

Why: Continue visiting nodes level by level

Step 4: Remove 3 from queue and visit it; add its child 6 to queue

Visited: 1, 2, 3
Queue: [4 -> 5 -> 6]

Why: Visit all nodes in current level before moving deeper

Step 5: Remove 4 from queue and visit it; no children to add

Visited: 1, 2, 3, 4
Queue: [5 -> 6]

Why: Leaf node visited, no children to enqueue

Step 6: Remove 5 from queue and visit it; no children to add

Visited: 1, 2, 3, 4, 5
Queue: [6]

Why: Leaf node visited, no children to enqueue

Step 7: Remove 6 from queue and visit it; no children to add

Visited: 1, 2, 3, 4, 5, 6
Queue: []

Why: Last node visited, traversal complete

Result:

Visited nodes in order: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Annotated Code

DSA Rust

use std::collections::VecDeque;

#[derive(Debug)]
struct TreeNode {
    val: i32,
    children: Vec<TreeNode>,
}

impl TreeNode {
    fn new(val: i32) -> Self {
        TreeNode { val, children: Vec::new() }
    }
}

fn level_order_bfs(root: &TreeNode) -> Vec<i32> {
    let mut result = Vec::new();
    let mut queue = VecDeque::new();
    queue.push_back(root);

    while let Some(node) = queue.pop_front() {
        result.push(node.val); // visit node
        for child in &node.children {
            queue.push_back(child); // enqueue children
        }
    }
    result
}

fn main() {
    // Build tree:
    //       1
    //     /   \
    //    2     3
    //   / \     \
    //  4   5     6

    let mut root = TreeNode::new(1);
    let mut node2 = TreeNode::new(2);
    let mut node3 = TreeNode::new(3);
    let node4 = TreeNode::new(4);
    let node5 = TreeNode::new(5);
    let node6 = TreeNode::new(6);

    node2.children.push(node4);
    node2.children.push(node5);
    node3.children.push(node6);

    root.children.push(node2);
    root.children.push(node3);

    let traversal = level_order_bfs(&root);
    for val in traversal {
        print!("{} -> ", val);
    }
    print!("null\n");
}

queue.push_back(root);

enqueue root node to start BFS

while let Some(node) = queue.pop_front() {

loop until queue is empty, processing nodes level by level

result.push(node.val);

visit current node and record its value

for child in &node.children { queue.push_back(child); }

enqueue all children of current node for next level

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) because each node is visited exactly once

Space: O(w) where w is the maximum width of the tree, due to the queue

vs Alternative: Compared to depth-first search, BFS uses more memory but visits nodes level by level, which is useful for shortest path or level-based problems

Edge Cases

Empty tree (root is None)

Returns empty traversal list

DSA Rust

Handle None before calling level_order_bfs; current code assumes root is valid

Tree with only root node

Returns list with single root value

DSA Rust

while let Some(node) = queue.pop_front() { ... } handles single node gracefully

Nodes with no children (leaf nodes)

Leaf nodes are visited and no children are enqueued

DSA Rust

for child in &node.children { queue.push_back(child); } skips empty children vector

When to Use This Pattern

When a problem asks to visit nodes level by level or find shortest path in a tree, use BFS with a queue to process nodes in order of their depth.

Common Mistakes

Mistake: Using recursion instead of a queue, which leads to depth-first traversal instead of level order
Fix: Use a queue data structure to hold nodes of the current level and process them in FIFO order

Mistake: Not enqueuing all children of a node, missing nodes in traversal
Fix: Ensure all children are added to the queue inside the loop visiting each node

Summary

Visits all nodes in a tree level by level from top to bottom.

Use when you need to process nodes in order of their depth or find shortest paths in trees.

The key is to use a queue to hold nodes of the current level before moving to the next.

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