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

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