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.add(node.value); inorder(node.right)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.

Basic Implementation

basic.kt
Replay: real traced execution (multi-file project)
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 = "]"))
}

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

    27val output = mutableListOf<Int>()28inorder(nodes, root, output)
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    11inorder(nodes, nodes[node].left, output)12output.add(nodes[node].value)13inorder(nodes, nodes[node].right, output)
    values this step[] → [1]output

  3. output ← [1, 2]

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

  4. output ← [1, 2, 3]

    11inorder(nodes, nodes[node].left, output)12output.add(nodes[node].value)13inorder(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.add(nodes[node].value)13inorder(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.add(nodes[node].value)13inorder(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.add(nodes[node].value)13inorder(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.add(nodes[node].value)13inorder(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]

    28	inorder(nodes, root, output)29	println(output.joinToString(prefix = "[", postfix = "]"))30}
    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

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