Trees

Level-Order Traversal

Visit a tree breadth-first with a queue.

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.

level order Level-order traversal uses a queue to visit shallower nodes first.

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: ", ") + "]" }
var queue: [Node] = [sampleTree()]
var output: [Int] = []
while !queue.isEmpty { let node = queue.removeFirst(); output.append(node.value); if let left = node.left { queue.append(left) }; if let right = node.right { queue.append(right) } }
print(listString(output))

  1. tree ← 4(2(1,3),6(5,7)), queue ← [4]

    1final class Node {2    let value: Int
    values this step4(2(1,3),6(5,7))tree[4]queue

  2. output ← [4], queue ← [2, 6]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4]output[2, 6]queue4dequeued

  3. output ← [4, 2], queue ← [6, 1, 3]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2]output[6, 1, 3]queue2dequeued

  4. output ← [4, 2, 6], queue ← [1, 3, 5, 7]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2, 6]output[1, 3, 5, 7]queue6dequeued

  5. output ← [4, 2, 6, 1], queue ← [3, 5, 7]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2, 6, 1]output[3, 5, 7]queue1dequeued

  6. output ← [4, 2, 6, 1, 3], queue ← [5, 7]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2, 6, 1, 3]output[5, 7]queue3dequeued

  7. output ← [4, 2, 6, 1, 3, 5], queue ← [7]

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2, 6, 1, 3, 5]output[7]queue5dequeued

  8. output ← [4, 2, 6, 1, 3, 5, 7], queue ← []

    15func listString(_ values: [Int]) -> String { return "[" + values.map(String.init).joined(separator: ", ") + "]" }16var queue: [Node] = [sampleTree()]17var output: [Int] = []
    values this step[4, 2, 6, 1, 3, 5, 7]output[]queue7dequeued

  9. print(listString(output))

    18while !queue.isEmpty { let node = queue.removeFirst(); output.append(node.value); if let left = node.left { queue.append(left) }; if let right = node.right { queue.append(right) } }19print(listString(output))
    values this step[4, 2, 6, 1, 3, 5, 7]output

Complexity

  • Time: O(n)
  • Space: O(w) queue space

Implementation notes

  • final class Node uses reference semantics with let value: Int and optional child links left: Node? and right: Node?.
  • var queue: [Node] = [sampleTree()] stores node references in a mutable Swift array; the initial queue contains the root 4.
  • var output: [Int] = [] records visited values separately from the queued nodes.
  • The traversal loop runs while !queue.isEmpty, then uses let node = queue.removeFirst() to dequeue the front node. On Swift Array, front removal shifts remaining elements and is linear in the queue length.
  • Each visited node appends node.value to output, then if let left and if let right unwrap optional children before queue.append(...).
  • The trace shows the queue by node values: [4], then [2, 6], then [6, 1, 3], then [1, 3, 5, 7], and finally drains to [].
  • The output grows in level order as [4], [4, 2], [4, 2, 6], and ends at [4, 2, 6, 1, 3, 5, 7].
  • listString(_:) formats the Int array with comma separators, so print(listString(output)) writes [4, 2, 6, 1, 3, 5, 7].