Tree Traversal Level Order BFS in DSA Rust - Execution Trace

Concept Flow - Tree Traversal Level Order BFS

Start at root node

↓

Add root to queue

↓

While queue not empty

↓

Remove front node from queue

↓

Visit node (process value)

↓

Add left child to queue if exists

↓

Add right child to queue if exists

↓

Repeat loop until queue empty

↓

Traversal complete

Start from the root, use a queue to visit nodes level by level, adding children to the queue as you go.

Execution Sample

DSA Rust

use std::collections::VecDeque;

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

fn level_order_bfs(root: Option<&Node>) {
    let mut queue = VecDeque::new();
    if let Some(r) = root {
        queue.push_back(r);
    }
    while let Some(node) = queue.pop_front() {
        println!("{}", node.val);
        if let Some(ref left) = node.left {
            queue.push_back(left.as_ref());
        }
        if let Some(ref right) = node.right {
            queue.push_back(right.as_ref());
        }
    }
}

This code visits each node of a binary tree level by level using a queue.

Execution Table

Step	Operation	Node Visited	Queue Before	Queue After	Visual State
1	Start at root	None	[]	[1]	1
2	Pop front	1	[1]	[]	1
3	Visit node	1	[]	[]	Visited: 1
4	Add left child	1	[]	[2]	1 -> 2
5	Add right child	1	[2]	[2, 3]	1 -> 2 -> 3
6	Pop front	2	[2, 3]	[3]	1 -> 2 -> 3
7	Visit node	2	[3]	[3]	Visited: 1, 2
8	Add left child	2	[3]	[3, 4]	1 -> 2 -> 3 -> 4
9	Add right child	2	[3, 4]	[3, 4, 5]	1 -> 2 -> 3 -> 4 -> 5
10	Pop front	3	[3, 4, 5]	[4, 5]	1 -> 2 -> 3 -> 4 -> 5
11	Visit node	3	[4, 5]	[4, 5]	Visited: 1, 2, 3
12	Add left child	3	[4, 5]	[4, 5] (no left child)	Visited: 1, 2, 3
13	Add right child	3	[4, 5]	[4, 5] (no right child)	Visited: 1, 2, 3
14	Pop front	4	[4, 5]	[5]	1 -> 2 -> 3 -> 4 -> 5
15	Visit node	4	[5]	[5]	Visited: 1, 2, 3, 4
16	Add left child	4	[5]	[5] (no left child)	Visited: 1, 2, 3, 4
17	Add right child	4	[5]	[5] (no right child)	Visited: 1, 2, 3, 4
18	Pop front	5	[5]	[]	1 -> 2 -> 3 -> 4 -> 5
19	Visit node	5	[]	[]	Visited: 1, 2, 3, 4, 5
20	Add left child	5	[]	[] (no left child)	Visited: 1, 2, 3, 4, 5
21	Add right child	5	[]	[] (no right child)	Visited: 1, 2, 3, 4, 5
22	Queue empty	None	[]	[]	Traversal complete

💡 Queue is empty, all nodes visited

Variable Tracker

Variable	Start	After Step 1	After Step 5	After Step 9	After Step 13	After Step 17	After Step 21	Final
queue	[]	[1]	[2, 3]	[3, 4, 5]	[4, 5]	[5]	[]	[]
visited_nodes	[]	[]	[1]	[1, 2]	[1, 2, 3]	[1, 2, 3, 4]	[1, 2, 3, 4, 5]	[1, 2, 3, 4, 5]

Key Moments - 3 Insights

Why do we add children to the queue after visiting the node?

Because in BFS, we visit nodes level by level. Adding children after visiting ensures we process all nodes at the current level before moving deeper. See steps 4,5,8,9 where children are added after visiting nodes in steps 3 and 7.

Why does the queue start with the root node only?

The queue holds nodes to visit next. We start with the root because it's the first node in the tree. Step 1 shows the queue initialized with the root node.

What happens when a node has no children?

No new nodes are added to the queue, so the queue size decreases. Steps 12,13 and 16,17 show no children added, queue shrinks until empty.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue after step 9?

A [3, 4, 5]

B [4, 5]

C [2, 3]

D [5]

💡 Hint

Check the 'Queue After' column at step 9 in the execution_table.

At which step does the queue become empty?

A Step 20

B Step 18

C Step 22

D Step 14

💡 Hint

Look for the step where 'Queue After' is empty and operation says 'Queue empty'.

If node 3 had a left child, how would the queue change after step 12?

A Queue would be empty after step 12

B Queue would include the new left child after step 12

C Queue would remove node 4 after step 12

D Queue would not change

💡 Hint

Step 12 shows no left child added; adding one would add it to the queue.

Concept Snapshot

Level Order BFS visits tree nodes level by level.
Use a queue to hold nodes to visit next.
Start by adding root to queue.
Pop front node, visit it, add its children to queue.
Repeat until queue is empty.
Result: nodes visited in breadth-first order.

Full Transcript

Level Order BFS traversal starts at the root node and uses a queue to visit nodes level by level. Initially, the root is added to the queue. Then, while the queue is not empty, the front node is removed and visited. Its left and right children, if any, are added to the queue. This process repeats until all nodes are visited and the queue is empty. The execution table shows each step, the node visited, the queue before and after, and the visual state of the tree traversal. The variable tracker records the queue contents and visited nodes after key steps. Key moments clarify why children are added after visiting nodes, why the queue starts with the root, and what happens when nodes have no children. The visual quiz tests understanding of queue states and effects of adding children. The concept snapshot summarizes the BFS traversal process in simple steps.

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