Trees

Build a Binary Tree

Create a fixed seven-node binary tree and render its shape.

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.

node links A node stores one value plus references to its left and right children.

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: ", ") + "]" }
let root = sampleTree()
print(render(root))

  1. node ← 1, tree ← 1

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step1node1tree

  2. node ← 3, tree ← 1, 3

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step3node1, 3tree

  3. node ← 2, tree ← 2(1,3)

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step2node2(1,3)tree

  4. node ← 5, tree ← 2(1,3), 5

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step5node2(1,3), 5tree

  5. node ← 7, tree ← 2(1,3), 5, 7

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step7node2(1,3), 5, 7tree

  6. node ← 6, tree ← 2(1,3), 6(5,7)

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step6node2(1,3), 6(5,7)tree

  7. node ← 4, tree ← 4(2(1,3),6(5,7))

    12func sampleTree() -> Node {13    return Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))14}
    values this step4node4(2(1,3),6(5,7))tree

  8. stdout ← 4(2(1,3),6(5,7))

    16let root = sampleTree()17print(render(root))
    values this step4(2(1,3),6(5,7))stdout4(2(1,3),6(5,7))tree

Complexity

  • Time: O(n)
  • Space: O(n)

Implementation notes

  • final class Node gives the tree reference semantics; each node stores a let value: Int and mutable optional child links left: Node? and right: Node?.
  • init(_ value: Int, _ left: Node? = nil, _ right: Node? = nil) lets leaf nodes omit children, leaving both links as nil.
  • sampleTree() -> Node builds the whole tree with nested constructor calls: leaves 1 and 3, then parent 2; leaves 5 and 7, then parent 6; finally root 4 with those two subtrees.
  • let root = sampleTree() binds the completed root reference; the checked source does not mutate it after construction.
  • render(_ node: Node?) -> String unwraps optional nodes with guard; nil children render as _, leaves render as just their value, and internal nodes render as value(left,right).
  • The trace follows the construction order from nodes 1, 3, 2, 5, 7, 6, to root 4, ending at 4(2(1,3),6(5,7)).
  • print(render(root)) outputs exactly 4(2(1,3),6(5,7)).