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.

Basic Implementation

basic.go

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)) }

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].

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