Level-Order Traversal

Visit a tree breadth-first with a queue.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this C# DSA implementation can be compared directly with the rest of the DSA track.

level order Level-order traversal uses a queue to visit shallower nodes first.

Basic Implementation

                            basic.cs
                        
Replay: real traced execution (multi-file project)

                            using System;
using System.Collections.Generic;
using System.Linq;

class Node {
    public int Value;
    public Node? Left;
    public Node? Right;
    public Node(int value, Node? left = null, Node? right = null) { Value = value; Left = left; Right = right; }
}
class Program {
    static string Render(Node? node) {
        if (node == null) return "_";
        if (node.Left == null && node.Right == null) return node.Value.ToString();
        return $"{node.Value}({Render(node.Left)},{Render(node.Right)})";
    }
    static Node SampleTree() => new Node(4, new Node(2, new Node(1), new Node(3)), new Node(6, new Node(5), new Node(7)));
    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";
    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }
}

                        
1tree ← 4(2(1,3),6(5,7)), queue ← [4]1using System;2using System.Collections.Generic;⋯values this step4(2(1,3),6(5,7))tree[4]queue
2output ← [4], queue ← [2, 6]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4]output[2, 6]queue4dequeued
3output ← [4, 2], queue ← [6, 1, 3]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2]output[6, 1, 3]queue2dequeued
4output ← [4, 2, 6], queue ← [1, 3, 5, 7]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued
5output ← [4, 2, 6, 1], queue ← [3, 5, 7]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued
6output ← [4, 2, 6, 1, 3], queue ← [5, 7]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued
7output ← [4, 2, 6, 1, 3, 5], queue ← [7]⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued
8output ← [4, 2, 6, 1, 3, 5, 7], queue ← []⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued
9static void Main() { var queue = new Queue<Node>(); queue.Enqueue(Samp…⋯18    static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19    static void Main() { var queue = new Queue<Node>(); queue.Enqueue(SampleTree()); var output = new List<int>(); while (queue.Count > 0) { var node = queue.Dequeue(); output.Add(node.Value); if (node.Left != null) queue.Enqueue(node.Left); if (node.Right != null) queue.Enqueue(node.Right); } Console.WriteLine(ListString(output)); }20}values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

Time: O(n)
Space: O(w) queue space

Implementation notes

Render tree structure explicitly instead of printing node objects.
Node is a class, so the Queue<Node> stores managed references to tree nodes allocated by the CLR and reclaimed by GC. Left and Right are nullable links; the node.Left != null / node.Right != null checks keep absent children out of the queue.
Queue<Node>.Dequeue() is guarded by queue.Count > 0, and List<int> grows as visited values are appended for deterministic rendering.
The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.