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].

in-order recursion `inorder(node.left); output << node.value; inorder(node.right)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.

Basic Implementation

basic.rb
Replay: real traced execution (multi-file project)
TreeNode = Struct.new(:value, :left, :right)

def make_node(nodes, value, left, right)
	idx = nodes.length
	nodes << TreeNode.new(value, left, right)
	idx
end

def inorder(nodes, node, output)
	if node != -1
		inorder(nodes, nodes[node].left, output)
		output << nodes[node].value
		inorder(nodes, nodes[node].right, output)
	end
end

nodes = []
n1 = make_node(nodes, 1, -1, -1)
n3 = make_node(nodes, 3, -1, -1)
n2 = make_node(nodes, 2, n1, n3)
n5 = make_node(nodes, 5, -1, -1)
n7 = make_node(nodes, 7, -1, -1)
n6 = make_node(nodes, 6, n5, n7)
root = make_node(nodes, 4, n2, n6)

output = []
inorder(nodes, root, output)
puts output.inspect

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

    26output = []27inorder(nodes, root, output)
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[] → [1]output

  3. output ← [1, 2]

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1, 2] → [1, 2, 3]output

  5. output ← [1, 2, 3, 4]

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1, 2, 3] → [1, 2, 3, 4]output

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

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1, 2, 3, 4] → [1, 2, 3, 4, 5]output

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

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]output

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

    11inorder(nodes, nodes[node].left, output)12output << nodes[node].value13inorder(nodes, nodes[node].right, output)
    values this step[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]output

  9. stdout ← [1, 2, 3, 4, 5, 6, 7]

    27inorder(nodes, root, output)28puts output.inspect
    values this step[1, 2, 3, 4, 5, 6, 7]stdout[1, 2, 3, 4, 5, 6, 7]output

Complexity

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

Implementation notes

  • Ruby: a small TreeNode = Struct.new(:value, :left, :right) stored in a plain Array arena. The arena pattern keeps the recursion focused on traversal without leaning on recursive class references or nil checks via Object#nil?.
  • The output buffer is a plain Array so the << growth is visible to the caller; the lesson does not lean on Enumerable#flat_map or a yielding Enumerator.
  • The replay shows the running output list and the visited node value on each visit frame, with node(<value>) labels instead of runtime references.