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.kt 
class TreeNode(var value: Int, var left: Int, var right: Int)

fun makeNode(nodes: MutableList<TreeNode>, value: Int, left: Int, right: Int): Int {
	val idx = nodes.size
	nodes.add(TreeNode(value, left, right))
	return idx
}

fun inorder(nodes: MutableList<TreeNode>, node: Int, output: MutableList<Int>) {
	if (node != -1) {
		inorder(nodes, nodes[node].left, output)
		output.add(nodes[node].value)
		inorder(nodes, nodes[node].right, output)
	}
}

fun main() {
	val nodes = mutableListOf<TreeNode>()
	val n1 = makeNode(nodes, 1, -1, -1)
	val n3 = makeNode(nodes, 3, -1, -1)
	val n2 = makeNode(nodes, 2, n1, n3)
	val n5 = makeNode(nodes, 5, -1, -1)
	val n7 = makeNode(nodes, 7, -1, -1)
	val n6 = makeNode(nodes, 6, n5, n7)
	val root = makeNode(nodes, 4, n2, n6)

	val output = mutableListOf<Int>()
	inorder(nodes, root, output)
	println(output.joinToString(prefix = "[", postfix = "]"))
}

Complexity

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

Implementation notes

  • Kotlin: a small class TreeNode(var value: Int, var left: Int, var right: Int) stored in a MutableList<TreeNode> arena. The arena pattern keeps the recursion focused on traversal without leaning on java.util.LinkedList or recursive class references.
  • The output buffer is a plain MutableList<Int> so the add 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.add(node.value); inorder(node.right)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.