Trees

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.

Basic Implementation

basic.swift 
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))

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].
preorder Preorder records the current node before visiting left and right subtrees.