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.

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: ", ") + "]" }
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))

Complexity

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

Implementation notes

  • Render tree structure explicitly instead of printing node objects.
  • The replay highlights the node, traversal state, queue, path, or search cursor that changes at each step.
level order Level-order traversal uses a queue to visit shallower nodes first.