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 Go 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.go
                        
Replay: real traced execution (multi-file project)

                            package main

import (
    "fmt"
    "strings"
)

type Node struct { value int; left *Node; right *Node }
func render(node *Node) string {
    if node == nil { return "_" }
    if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }
    return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))
}
func sampleTree() *Node {
    return &Node{4, &Node{2, &Node{1, nil, nil}, &Node{3, nil, nil}}, &Node{6, &Node{5, nil, nil}, &Node{7, nil, nil}}}
}
func listString(values []int) string {
    parts := []string{}
    for _, value := range values { parts = append(parts, fmt.Sprintf("%d", value)) }
    return "[" + strings.Join(parts, ", ") + "]"
}
func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }
func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1package main⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[] → [4]output4node
3output ← [4, 2]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(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]⋯21}22func preorder(node *Node, output *[]int) { if node == nil { return }; *output = append(*output, node.value); preorder(node.left, output); preorder(node.right, output) }23func main() { output := []int{}; preorder(sampleTree(), &output); fmt.Println(listString(output)) }values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9if node.left == nil && node.right == nil { return fmt.Sprintf("%d", no…⋯10if node == nil { return "_" }11if node.left == nil && node.right == nil { return fmt.Sprintf("%d", node.value) }12return fmt.Sprintf("%d(%s,%s)", node.value, render(node.left), render(node.right))⋯values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

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

Implementation notes

Go uses type Node struct { value int; left *Node; right *Node }, and preorder receives *Node pointers from the fixed sampleTree.
preorder(node *Node, output *[]int) uses if node == nil { return } as the base case before reading node.value.
The visit step mutates the caller's output slice through the pointer: *output = append(*output, node.value). This matters because append can return a new slice header if the backing array grows.
The recursive call order is current node, preorder(node.left, output), then preorder(node.right, output), so stack frames carry the current node pointer and the shared output-slice pointer.
The trace records the visit sequence and output states: [4], [4, 2], [4, 2, 1], [4, 2, 1, 3], [4, 2, 1, 3, 6], [4, 2, 1, 3, 6, 5], and [4, 2, 1, 3, 6, 5, 7].
listString formats the collected int values with fmt.Sprintf and strings.Join; fmt.Println(listString(output)) prints [4, 2, 1, 3, 6, 5, 7].