Tree Traversal Level Order BFS in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a queue for BFS traversal.

DSA C#

Queue<TreeNode> queue = new [1]<TreeNode>();

Drag options to blanks, or click blank then click option'

AQueue

BStack

CList

DDictionary

Attempts:

3 left

💡 Hint

Common Mistakes

Using Stack instead of Queue causes wrong traversal order.

Using List or Dictionary does not provide FIFO behavior.

We use a Queue to hold nodes for level order traversal (BFS).

2fill in blank

medium

Complete the code to enqueue the root node before starting BFS.

DSA C#

if (root != null) queue.[1](root);

Drag options to blanks, or click blank then click option'

APop

BEnqueue

CPush

DAdd

Attempts:

3 left

💡 Hint

Common Mistakes

Using Push or Pop which are stack operations.

Using Add which is not a queue method.

We add the root node to the queue using Enqueue to start BFS.

3fill in blank

hard

Fix the error in the loop condition to continue BFS while queue is not empty.

DSA C#

while (queue.[1] > 0) { /* BFS logic */ }

Drag options to blanks, or click blank then click option'

ACount

BLength

CSize

DCapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using Length or Size causes compile errors.

Using Capacity checks reserved space, not current elements.

The Count property gives the number of elements in the queue.

4fill in blank

hard

Fill both blanks to dequeue a node and add its children to the queue.

DSA C#

TreeNode current = queue.[1]();
if (current.[2] != null) queue.Enqueue(current.left);

Drag options to blanks, or click blank then click option'

ADequeue

BPop

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using Pop which is for stacks.

Checking right child instead of left in this line.

Use Dequeue() to remove the front node, then check left child to enqueue.

5fill in blank

hard

Fill all three blanks to add the right child if it exists.

DSA C#

if (current.[1] != null) queue.[2](current.[3]);

Drag options to blanks, or click blank then click option'

Aright

BEnqueue

DDequeue

Attempts:

3 left

💡 Hint

Common Mistakes

Using Dequeue instead of Enqueue.

Checking left child instead of right here.

Check if right child exists, then Enqueue it to the queue.

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