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.lua 
local function make_node(nodes, value, left, right)
	local idx = #nodes + 1
	nodes[idx] = {value = value, left = left, right = right}
	return idx
end

local function inorder(nodes, node, output)
	if node ~= -1 then
		inorder(nodes, nodes[node].left, output)
		output[#output + 1] = nodes[node].value
		inorder(nodes, nodes[node].right, output)
	end
end

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

local output = {}
inorder(nodes, root, output)
io.write("[")
for i = 1, #output do
	if i > 1 then io.write(", ") end
	io.write(tostring(output[i]))
end
io.write("]\n")

Complexity

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

Implementation notes

  • Lua: a tiny table node {value = ..., left = ..., right = ...} stored in a plain integer-keyed nodes arena. The arena pattern keeps the recursion focused on traversal without leaning on metatables to fake an object reference graph.
  • The output buffer is a plain table grown with output[#output + 1] = ...; Lua passes tables by reference, so the caller sees the appended values without an explicit return path.
  • 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(nodes, node.left, output); output[#output + 1] = node.value; inorder(nodes, node.right, output)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.