Tree Traversal Level Order BFS in DSA C#

Mental Model

We visit tree nodes level by level from top to bottom, left to right. This way, we see all nodes on one level before moving to the next.

Analogy: Imagine standing on the first floor of a building and looking at all rooms there before going up to the second floor and checking all rooms there, and so on.

      1
     / \
    2   3
   / \   \
  4   5   6

Level order: 1 -> 2 -> 3 -> 4 -> 5 -> 6

Dry Run Walkthrough

Input: Binary tree: 1 as root, 2 and 3 as children of 1, 4 and 5 as children of 2, 6 as right child of 3

Goal: Print nodes level by level from top to bottom, left to right

Step 1: Start with root node 1 in queue

Queue: [1]
Output: []

Why: We begin traversal from the root node

Step 2: Remove 1 from queue, add its value to output, enqueue its children 2 and 3

Queue: [2, 3]
Output: [1]

Why: Visit root, then prepare to visit its children next

Step 3: Remove 2 from queue, add its value to output, enqueue its children 4 and 5

Queue: [3, 4, 5]
Output: [1, 2]

Why: Visit next node on level 2, then enqueue its children

Step 4: Remove 3 from queue, add its value to output, enqueue its child 6

Queue: [4, 5, 6]
Output: [1, 2, 3]

Why: Visit next node on level 2, enqueue its child

Step 5: Remove 4 from queue, add its value to output, no children to enqueue

Queue: [5, 6]
Output: [1, 2, 3, 4]

Why: Visit next node on level 3, no children to add

Step 6: Remove 5 from queue, add its value to output, no children to enqueue

Queue: [6]
Output: [1, 2, 3, 4, 5]

Why: Visit next node on level 3, no children to add

Step 7: Remove 6 from queue, add its value to output, no children to enqueue

Queue: []
Output: [1, 2, 3, 4, 5, 6]

Why: Visit last node, traversal complete

Result:

Output: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Annotated Code

DSA C#

using System;
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;
    }
}

public class Solution {
    public static void LevelOrderTraversal(TreeNode root) {
        if (root == null) return; // handle empty tree
        Queue<TreeNode> queue = new Queue<TreeNode>();
        queue.Enqueue(root); // start with root
        while (queue.Count > 0) {
            TreeNode current = queue.Dequeue(); // visit front node
            Console.Write(current.val + " -> ");
            if (current.left != null) queue.Enqueue(current.left); // enqueue left child
            if (current.right != null) queue.Enqueue(current.right); // enqueue right child
        }
        Console.WriteLine("null");
    }

    public static void Main() {
        TreeNode root = new TreeNode(1,
            new TreeNode(2, new TreeNode(4), new TreeNode(5)),
            new TreeNode(3, null, new TreeNode(6))
        );
        LevelOrderTraversal(root);
    }
}

if (root == null) return; // handle empty tree

stop if tree is empty

queue.Enqueue(root); // start with root

initialize queue with root node

TreeNode current = queue.Dequeue(); // visit front node

remove node from front to process it

Console.Write(current.val + " -> ");

print current node's value

if (current.left != null) queue.Enqueue(current.left); // enqueue left child

add left child to queue if exists

if (current.right != null) queue.Enqueue(current.right); // enqueue right child

add right child to queue if exists

Output

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null

Complexity Analysis

Time: O(n) because we visit each node exactly once

Space: O(n) because in worst case the queue holds all nodes at the largest level

vs Alternative: Compared to depth-first traversals, BFS uses extra space for the queue but gives level order output directly

Edge Cases

Empty tree

Function returns immediately without printing

DSA C#

if (root == null) return; // handle empty tree

Tree with only root node

Prints root value followed by null

DSA C#

queue.Enqueue(root); // start with root

Tree with missing children

Only existing children are enqueued and printed

DSA C#

if (current.left != null) queue.Enqueue(current.left);

When to Use This Pattern

When a problem asks to visit nodes level by level or find shortest path in a tree, use BFS with a queue to process nodes in order.

Common Mistakes

Mistake: Not enqueuing children correctly causing incomplete traversal
Fix: Always check if left and right children exist before enqueueing

Mistake: Printing nodes before dequeueing causing wrong order
Fix: Dequeue node first, then print its value

Summary

Visits all nodes in a tree level by level from top to bottom, left to right.

Use when you need to process or print nodes in order of their depth or find shortest paths.

The key is to use a queue to hold nodes of the current level before moving to the next.

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