Tree Traversal Level Order BFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Level Order Traversal on a Binary Tree

What is the output of the following C# code performing level order traversal (BFS) on the given binary tree?

DSA C#

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

public class Program {
    public static void LevelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        while (q.Count > 0) {
            Node current = q.Dequeue();
            Console.Write(current.val + " ");
            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
        }
    }

    public static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        LevelOrder(root);
    }
}

A 1 3 2 6 5 4

B 1 2 3 4 5 6

C 4 5 6 2 3 1

D 1 2 4 5 3 6

💡 Hint

Remember, level order traversal visits nodes level by level from left to right.

The code uses a queue to visit nodes level by level.

Starting from root (1), it visits nodes in this order: 1, then 2 and 3, then 4, 5, and 6.

❓ Predict Output

intermediate

Level Order Traversal Output with Null Children

What will be printed by this C# code performing level order traversal on a binary tree with some null children?

DSA C#

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

public class Program {
    public static void LevelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        while (q.Count > 0) {
            Node current = q.Dequeue();
            Console.Write(current.val + " ");
            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
        }
    }

    public static void Main() {
        Node root = new Node(10);
        root.left = new Node(20);
        root.right = null;
        root.left.left = null;
        root.left.right = new Node(30);
        LevelOrder(root);
    }
}

A 10 20 30

B 10 20

C 20 10 30

D 10 30 20

💡 Hint

Nodes with null children are skipped in the queue.

The traversal visits root (10), then its left child (20), then 20's right child (30).

Null children are not enqueued.

🧠 Conceptual

advanced

Understanding Queue Usage in Level Order Traversal

Why is a queue used in level order traversal (BFS) of a binary tree instead of a stack?

A Because a queue uses less memory than a stack for tree traversal.

B Because a stack cannot store tree nodes.

C Because a queue processes nodes in first-in-first-out order, preserving the level order sequence.

D Because a stack processes nodes in first-in-first-out order, which is needed for BFS.

💡 Hint

Think about the order nodes are visited in BFS.

BFS visits nodes level by level, so nodes must be processed in the order they were discovered.

A queue ensures first-in-first-out order, which matches this requirement.

❓ Predict Output

advanced

Output of Level Order Traversal with Modified Enqueue Order

What is the output of this C# code where the right child is enqueued before the left child during level order traversal?

DSA C#

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

public class Program {
    public static void LevelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        while (q.Count > 0) {
            Node current = q.Dequeue();
            Console.Write(current.val + " ");
            if (current.right != null) q.Enqueue(current.right);
            if (current.left != null) q.Enqueue(current.left);
        }
    }

    public static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.right = new Node(6);
        LevelOrder(root);
    }
}

A 1 3 2 6 5 4

B 1 2 3 4 5 6

C 1 2 3 5 4 6

D 1 3 2 4 5 6

💡 Hint

Enqueuing right child before left reverses the order of nodes at each level.

Since right child is enqueued before left, nodes at each level are visited from right to left.

Traversal order: 1, then 3 and 2, then 6, 5, and 4.

🔧 Debug

expert

Identify the Error in Level Order Traversal Implementation

What error will this C# code produce when performing level order traversal on a binary tree?

DSA C#

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public Node left, right;
    public Node(int v) { val = v; left = right = null; }
}

public class Program {
    public static void LevelOrder(Node root) {
        if (root == null) return;
        Queue<Node> q = new Queue<Node>();
        q.Enqueue(root);
        while (q.Count > 0) {
            Node current = q.Dequeue();
            Console.Write(current.val + " ");
            if (current.left != null) q.Enqueue(current.left);
            if (current.right != null) q.Enqueue(current.right);
            q.Dequeue();
        }
    }

    public static void Main() {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        LevelOrder(root);
    }
}

A No error, prints: 1 2 3

B NullReferenceException when accessing current.val

C StackOverflowException due to infinite recursion

D InvalidOperationException due to dequeueing from empty queue

💡 Hint

Check the extra dequeue inside the while loop.

The extra q.Dequeue() inside the loop removes an element without processing it.

This causes the queue to become empty prematurely, leading to an InvalidOperationException when trying to dequeue from an empty 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