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

                            final class Node {
    let value: Int
    var left: Node?
    var right: Node?
    init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) { self.value = value; self.left = left; self.right = right }
}
func render(_ node: Node?) -> String {
    guard let node = node else { return "_" }
    if node.left == nil && node.right == nil { return String(node.value) }
    return "\(node.value)(\(render(node.left)),\(render(node.right)))"
}
func sampleTree() -> Node {
    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
}
func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }
func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }
var output: [Int] = []
preorder(sampleTree(), &output)
print(listString(output))

                        
1tree ← 4(2(1,3),6(5,7)), output ← []1final class Node {2    let value: Int⋯values this step4(2(1,3),6(5,7))tree[]output
2output ← [4]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[] → [4]output4node
3output ← [4, 2]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4] → [4, 2]output2node
4output ← [4, 2, 1]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4, 2] → [4, 2, 1]output1node
5output ← [4, 2, 1, 3]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4, 2, 1] → [4, 2, 1, 3]output3node
6output ← [4, 2, 1, 3, 6]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node
7output ← [4, 2, 1, 3, 6, 5]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node
8output ← [4, 2, 1, 3, 6, 5, 7]⋯15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16func preorder(_ node: Node?, _ output: inout [Int]) { guard let node = node else { return }; output.append(node.value); preorder(node.left, &output); preorder(node.right, &output) }17var output: [Int] = []⋯values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node
9print(listString(output))⋯18preorder(sampleTree(), &output)19print(listString(output))values this step[4, 2, 1, 3, 6, 5, 7]output

Complexity

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

Implementation notes

final class Node gives each tree node reference semantics, with let value: Int and optional child links left: Node? and right: Node?.
preorder(_ node: Node?, _ output: inout [Int]) accepts an optional node and mutates the caller's output array through inout.
The base case is guard let node = node else { return }, so nil child links return without adding a sentinel value.
The function appends before recursion: output.append(node.value), then preorder(node.left, &output), then preorder(node.right, &output).
var output: [Int] = [] starts empty, and preorder(sampleTree(), &output) walks the canonical 4(2(1,3),6(5,7)) tree.
The trace shows output growing step by step: [4], [4, 2], [4, 2, 1], [4, 2, 1, 3], then the right subtree [4, 2, 1, 3, 6, 5, 7].
listString(_:) formats the Int array with comma separators, so print(listString(output)) writes [4, 2, 1, 3, 6, 5, 7].