Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

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.

preorder Preorder records the current node before visiting left and right subtrees.

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 Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }
    static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }
}

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1using System;2using System.Collections.Generic;⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[] → [4]output4node
3output ← [4, 2]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯18static string ListString(IEnumerable<int> values) => "[" + string.Join(", ", values) + "]";19static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }⋯values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9static void Main() { var output = new List<int>(); Preorder(SampleTree…⋯19    static void Preorder(Node? node, List<int> output) { if (node == null) return; output.Add(node.Value); Preorder(node.Left, output); Preorder(node.Right, output); }20    static void Main() { var output = new List<int>(); Preorder(SampleTree(), output); Console.WriteLine(ListString(output)); }21}values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

Time: O(n)
Space: O(h) recursion stack

Implementation notes

Render tree structure explicitly instead of printing node objects.
Node is a class, so Left and Right are nullable managed references; SampleTree() allocates nodes through the CLR and they are reclaimed by GC. Preorder(Node? node, List<int> output) returns immediately on null, then appends the current value before recursing left and right on the C# call stack.
List<int> grows as output.Add(node.Value) records each visit, matching the trace frames that show output before and output after every node visit.
The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.