Tree Traversal Level Order BFS in DSA C# - 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

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

Execution Sample

DSA C#

Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while(queue.Count > 0) {
  TreeNode current = queue.Dequeue();
  Visit(current);
  if(current.Left != null) queue.Enqueue(current.Left);
  if(current.Right != null) queue.Enqueue(current.Right);
}

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

Execution Table

Step	Operation	Node Visited	Queue State (front->rear)	Visual Tree State
1	Start: Enqueue root	None	[1]	1 / \ 2 3 / \ 4 5
2	Dequeue and visit	1	[2, 3]	1 / \ 2 3 / \ 4 5
3	Dequeue and visit	2	[3, 4, 5]	1 / \ 2 3 / \ 4 5
4	Dequeue and visit	3	[4, 5]	1 / \ 2 3 / \ 4 5
5	Dequeue and visit	4	[5]	1 / \ 2 3 / \ 4 5
6	Dequeue and visit	5	[]	1 / \ 2 3 / \ 4 5
7	Queue empty, end	None	[]	1 / \ 2 3 / \ 4 5

💡 Queue is empty, all nodes visited in level order

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
queue	[]	[1]	[2,3]	[3,4,5]	[4,5]	[5]	[]	[]
current	null	null	1	2	3	4	5	null

Key Moments - 3 Insights

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

Because in BFS we visit nodes level by level, adding children after visiting ensures nodes on the same level are visited before going deeper. See execution_table steps 2-4 where children are enqueued after visiting.

Why does the loop stop when the queue is empty?

The queue holds nodes to visit. When empty, no nodes remain to visit. Execution_table step 7 shows queue empty means traversal is complete.

Why do we use a queue and not a stack for level order traversal?

A queue processes nodes in the order they were added (FIFO), which matches level order visiting. A stack (LIFO) would visit nodes depth-first, not level order. The queue state in execution_table shows nodes processed in insertion order.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what nodes are currently in the queue?

A [2, 3]

B [4, 5]

C [3, 4, 5]

D [5]

💡 Hint

Check the 'Queue State' column at Step 3 in the execution_table.

At which step does the queue become empty?

A Step 7

B Step 6

C Step 5

D Step 4

💡 Hint

Look at the 'Queue State' column and find when it shows [].

If the node 3 had a left child 6, when would 6 be added to the queue?

A After visiting node 3 (Step 4)

B At the start (Step 1)

C After visiting node 2 (Step 3)

D After visiting node 5 (Step 6)

💡 Hint

Children are enqueued immediately after visiting their parent node, see steps 2-4.

Concept Snapshot

Level Order BFS visits tree nodes level by level.
Use a queue to hold nodes to visit.
Start by enqueueing root.
While queue not empty: dequeue, visit, enqueue children.
Queue ensures FIFO order for correct level traversal.

Full Transcript

Level Order BFS traversal visits nodes of a tree one level at a time from top to bottom. We start by putting the root node into a queue. Then, while the queue has nodes, we take the front node out, visit it, and add its children to the back of the queue. This process repeats until the queue is empty, meaning all nodes have been visited. The queue keeps track of nodes to visit in the order they appear in the tree levels. This method ensures nodes are visited level by level, left to right. The example tree with nodes 1, 2, 3, 4, 5 shows how nodes enter and leave the queue step by step, confirming the level order traversal.

Practice

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

easy

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

B. Visits nodes in preorder (root, left, right)

C. Visits nodes in inorder (left, root, right)

D. Visits nodes in postorder (left, right, root)

Solution

1. Step 1: Understand Level Order Traversal

   Level order traversal visits nodes starting from the root, then all nodes at the next level, and so on, moving left to right at each level.

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 A

4. Quick Check:

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

Hint: Level order means visit nodes by levels, not depth [OK]

Common Mistakes:

• Confusing level order with preorder traversal
• Thinking level order is depth-first
• Mixing up left-to-right with right-to-left order

2. Which of the following C# code snippets correctly initializes a queue for level order traversal?

easy

A. Queue<TreeNode> queue = new Queue<TreeNode>();

B. List<TreeNode> queue = new List<TreeNode>();

C. Stack<TreeNode> queue = new Stack<TreeNode>();

D. Dictionary queue = new Dictionary();

Solution

1. Step 1: Identify the correct data structure for BFS

   BFS uses a queue to process nodes in FIFO order.

2. Step 2: Check the code snippet

   Queue<TreeNode> queue = new Queue<TreeNode>(); uses Queue<TreeNode>, which is correct. Others use List, Stack, or Dictionary, which are incorrect for BFS queue.

3. Final Answer:

   Queue<TreeNode> queue = new Queue<TreeNode>(); -> Option A

4. Quick Check:

   Queue for BFS = Queue<TreeNode> [OK]

Hint: BFS always uses a queue, not stack or list [OK]

Common Mistakes:

• Using Stack instead of Queue for BFS
• Using List which lacks FIFO behavior
• Confusing Dictionary with queue

3. What is the output of the following C# code performing level order traversal on this tree?

    1
   / \
  2   3
 /     \
4       5

// Code snippet:
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while(queue.Count > 0) {
  TreeNode node = queue.Dequeue();
  Console.Write(node.val + " ");
  if(node.left != null) queue.Enqueue(node.left);
  if(node.right != null) queue.Enqueue(node.right);
}

medium

A. 4 2 5 3 1

B. 1 2 3 4 5

C. 1 3 2 5 4

D. 2 4 3 5 1

Solution

1. Step 1: Trace the queue operations

   Start with root (1). Dequeue 1, enqueue 2 and 3. Output: 1 Dequeue 2, enqueue 4. Output: 1 2 Dequeue 3, enqueue 5. Output: 1 2 3 Dequeue 4, no children. Output: 1 2 3 4 Dequeue 5, no children. Output: 1 2 3 4 5

2. Step 2: Confirm output order

   The output matches level order: 1 2 3 4 5

3. Final Answer:

   1 2 3 4 5 -> Option B

4. Quick Check:

   Level order output = 1 2 3 4 5 [OK]

Hint: Follow queue enqueue/dequeue step-by-step [OK]

Common Mistakes:

• Mixing preorder with level order output
• Forgetting to enqueue children in correct order
• Printing nodes before dequeue

4. Identify the bug in this C# code snippet for level order traversal:

Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while(queue.Count > 0) {
  TreeNode node = queue.Dequeue();
  Console.Write(node.val + " ");
  if(node.left == null) queue.Enqueue(node.left);
  if(node.right == null) queue.Enqueue(node.right);
}

medium

A. It prints node values after enqueueing children

B. It enqueues null children causing runtime errors

C. It uses Stack instead of Queue

D. It never enqueues any children

Solution

1. Step 1: Analyze the if conditions for enqueue

   The code enqueues children only if node.left == null and node.right == null, which means it enqueues children only if they are null (no child).

2. Step 2: Understand the effect

   Since children are null, it never enqueues actual child nodes, so traversal stops after root.

3. Final Answer:

   It never enqueues any children -> Option D

4. Quick Check:

   Check conditions: should be != null, not == null [OK]

Hint: Enqueue children only if they are NOT null [OK]

Common Mistakes:

• Using == null instead of != null in conditions
• Enqueuing null nodes causing errors
• Confusing order of printing and enqueueing

5. Given a binary tree, how can you modify the level order traversal to return a list of lists, where each inner list contains nodes at that level?

hard

A. Traverse the tree inorder and group nodes by their values

B. Use recursion to visit nodes and store them by depth

C. Use a queue and track the number of nodes at each level, enqueue children accordingly

D. Use a stack to store nodes and pop them level by level

Solution

1. Step 1: Understand level grouping in BFS

   To group nodes by level, we process nodes level by level. We track how many nodes are at the current level before processing them.

2. Step 2: Implement queue with level size tracking

   At each iteration, get the queue size (number of nodes at current level), dequeue exactly that many nodes, enqueue their children, and store the dequeued nodes in a list for that level.

3. Final Answer:

   Use a queue and track the number of nodes at each level, enqueue children accordingly -> Option C

4. Quick Check:

   Level order + level size tracking = grouped levels [OK]

Hint: Track queue size each loop to separate levels [OK]

Common Mistakes:

• Using recursion without tracking depth
• Using stack which is LIFO, not suitable for level order
• Grouping nodes by value instead of level