Trees

In-Order Traversal (BST)

Recurse left, visit(node), recurse right. On a binary search tree, this emits values in ascending order — a useful invariant to teach.

Algorithm

Canonical tree 4(2(1, 3), 6(5, 7)) is a balanced BST. In-order traversal yields [1, 2, 3, 4, 5, 6, 7].

Basic Implementation

basic.swift 
struct TreeNode {
	var value: Int
	var left: Int
	var right: Int
}

func makeNode(_ nodes: inout [TreeNode], _ value: Int, _ left: Int, _ right: Int) -> Int {
	let idx = nodes.count
	nodes.append(TreeNode(value: value, left: left, right: right))
	return idx
}

func inorder(_ nodes: [TreeNode], _ node: Int, _ output: inout [Int]) {
	if node != -1 {
		inorder(nodes, nodes[node].left, &output)
		output.append(nodes[node].value)
		inorder(nodes, nodes[node].right, &output)
	}
}

var nodes: [TreeNode] = []
let n1 = makeNode(&nodes, 1, -1, -1)
let n3 = makeNode(&nodes, 3, -1, -1)
let n2 = makeNode(&nodes, 2, n1, n3)
let n5 = makeNode(&nodes, 5, -1, -1)
let n7 = makeNode(&nodes, 7, -1, -1)
let n6 = makeNode(&nodes, 6, n5, n7)
let root = makeNode(&nodes, 4, n2, n6)

var output: [Int] = []
inorder(nodes, root, &output)
print(output)

Complexity

  • Time: O(n)
  • Space: O(h) call stack

Implementation notes

  • Swift: a small struct TreeNode { var value: Int; var left: Int; var right: Int } stored in a var nodes: [TreeNode] arena. The arena pattern keeps the recursion focused on traversal without leaning on a class-based tree with shared references.
  • The output buffer is a plain var output: [Int] so the append growth is visible to the caller; the lesson does not lean on a sequence helper.
  • The replay shows the running output list and the visited node value on each visit frame, with node(<value>) labels instead of runtime references.
in-order recursion `inorder(node.left); output.append(node.value); inorder(node.right)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.