Tree Traversal Level Order BFS in DSA C# - Build from Scratch

Tree Traversal Level Order BFS

📖 Scenario: You are working with a simple family tree where each person can have up to two children. You want to visit each family member level by level, starting from the oldest ancestor.

🎯 Goal: Build a program that performs a level order traversal (Breadth-First Search) on a binary tree and prints the values of each node in order.

📋 What You'll Learn

Create a binary tree with specific nodes and values

Use a queue to help with level order traversal

Implement the BFS traversal logic

Print the node values in level order

💡 Why This Matters

🌍 Real World

Level order traversal is used in many real-world scenarios like finding the shortest path in maps, scheduling tasks, and organizing hierarchical data.

💼 Career

Understanding BFS and tree traversal is essential for software engineers working with data structures, algorithms, and system design.

1

Create the binary tree nodes

Create a class called TreeNode with an int property val, and two TreeNode properties left and right. Then create a root node called root with value 1, its left child with value 2, and its right child with value 3.

DSA C#

// Define TreeNode class and create root node with children
// Your code here

Hint

Define the TreeNode class first. Then create the root node with value 1 and assign its left and right children with values 2 and 3.

2

Set up a queue for BFS

Create a Queue<TreeNode> called queue and enqueue the root node.

DSA C#

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

// Create a queue and add root node
// Your code here

Hint

Use Queue<TreeNode> and call Enqueue to add the root node.

3

Implement the BFS traversal logic

Create a List<int> called result. Use a while loop that runs while queue.Count > 0. Inside the loop, dequeue a node into current, add current.val to result. If current.left is not null, enqueue it. If current.right is not null, enqueue it.

DSA C#

using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

Queue queue = new Queue();
queue.Enqueue(root);

// Create result list and implement BFS loop
// Your code here

Hint

Use a while loop to process nodes until the queue is empty. Dequeue nodes, add their values to result, and enqueue their children if they exist.

4

Print the BFS traversal result

Print the values in result separated by spaces using Console.WriteLine(string.Join(" ", result)).

DSA C#

using System.Collections.Generic;

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

TreeNode root = new TreeNode(1, new TreeNode(2), new TreeNode(3));

Queue queue = new Queue();
queue.Enqueue(root);

List result = new List();

while (queue.Count > 0)
{
    TreeNode current = queue.Dequeue();
    result.Add(current.val);
    if (current.left != null)
    {
        queue.Enqueue(current.left);
    }
    if (current.right != null)
    {
        queue.Enqueue(current.right);
    }
}

// Print the result list values separated by spaces
// Your code here

Hint

Use Console.WriteLine(string.Join(" ", result)) to print all values separated by spaces.

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