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

import scala.collection.mutable.ArrayBuffer

class TreeNode(var value: Int, var left: Int, var right: Int)

object Main {
	def makeNode(nodes: ArrayBuffer[TreeNode], value: Int, left: Int, right: Int): Int = {
		val idx = nodes.length
		nodes += new TreeNode(value, left, right)
		idx
	}

	def inorder(nodes: ArrayBuffer[TreeNode], node: Int, output: ArrayBuffer[Int]): Unit = {
		if (node != -1) {
			inorder(nodes, nodes(node).left, output)
			output += nodes(node).value
			inorder(nodes, nodes(node).right, output)
		}
	}

	def main(args: Array[String]): Unit = {
		val nodes = ArrayBuffer.empty[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 = ArrayBuffer.empty[Int]
		inorder(nodes, root, output)
		println(output.mkString("[", ", ", "]"))
	}
}

Complexity

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

Implementation notes

Scala: a small class TreeNode(var value: Int, var left: Int, var right: Int) stored in an ArrayBuffer[TreeNode] arena. The arena pattern keeps the recursion focused on traversal without leaning on recursive case class references or Option[TreeNode].
The output buffer is a plain ArrayBuffer[Int] so the += growth is visible to the caller; the lesson does not lean on a sequence helper like Seq.flatMap or for ... yield.
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.