Tree Traversal Level Order BFS in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does Level Order Traversal (BFS) of a binary tree mean?

It means visiting all nodes level by level from top to bottom and left to right within each level.

beginner

Which data structure is commonly used to implement Level Order Traversal?

A queue is used to keep track of nodes to visit in order, ensuring nodes are processed level by level.

beginner

In C#, how do you enqueue and dequeue nodes for BFS traversal?

Use Queue<TreeNode> queue = new Queue<TreeNode>(); then queue.Enqueue(node) to add and queue.Dequeue() to remove the front node.

intermediate

What is the time complexity of Level Order Traversal on a binary tree with n nodes?

The time complexity is O(n) because each node is visited exactly once.

beginner

Why is Level Order Traversal also called Breadth-First Search (BFS)?

Because it explores all nodes at the current depth before moving to nodes at the next depth, spreading out like a wave.

What data structure is essential for implementing Level Order Traversal?

A Stack

B Array

C Queue

D Linked List

Queue is used to process nodes in the order they are discovered, which fits level order traversal.

In Level Order Traversal, which node is visited first?

A Any random node

B Leftmost leaf node

C Rightmost leaf node

D Root node

Traversal starts from the root node at the top level.

What is the output order of nodes in Level Order Traversal for this tree? 1 / \ 2 3

A 1, 2, 3

B 2, 3, 1

C 3, 2, 1

D 1, 3, 2

Nodes are visited level by level: root (1), then left child (2), then right child (3).

What happens if you use a stack instead of a queue for Level Order Traversal?

A Traversal remains Level Order

B Traversal becomes Depth First Search

C Traversal visits nodes randomly

D Traversal stops immediately

Stack causes last-in-first-out order, which leads to Depth First Search behavior.

What is the space complexity of Level Order Traversal in the worst case?

A O(n)

B O(log n)

C O(1)

D O(n^2)

In the worst case, the queue can hold all nodes at the largest level, which can be up to O(n).

Explain how Level Order Traversal (BFS) works on a binary tree step-by-step.

Think about visiting nodes like visiting friends floor by floor in a building.

Describe the difference between Level Order Traversal and Depth First Traversal.

Compare exploring a tree floor by floor vs going deep down one branch first.

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