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

Basic Implementation

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

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

    30val output = ArrayBuffer.empty[Int]31inorder(nodes, root, output)
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(nodes, nodes(node).right, output)
    values this step[] → [1]output

  3. output ← [1, 2]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(nodes, nodes(node).right, output)
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(nodes, nodes(node).right, output)
    values this step[1, 2] → [1, 2, 3]output

  5. output ← [1, 2, 3, 4]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(nodes, nodes(node).right, output)
    values this step[1, 2, 3] → [1, 2, 3, 4]output

  6. output ← [1, 2, 3, 4, 5]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(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]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(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]

    14inorder(nodes, nodes(node).left, output)15output += nodes(node).value16inorder(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]

    31	inorder(nodes, root, output)32	println(output.mkString("[", ", ", "]"))33}
    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

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