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 `output <- inorder(nodes, node.left, output); output[length(output) + 1] <- node.value; output <- inorder(nodes, node.right, output)`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.

Basic Implementation

basic.R
Replay: real traced execution (multi-file project)
make_node <- function(nodes, value, left, right) {
	idx <- length(nodes) + 1
	nodes[[idx]] <- list(value = value, left = left, right = right)
	list(nodes = nodes, idx = idx)
}

inorder <- function(nodes, node, output) {
	if (node != -1) {
		output <- inorder(nodes, nodes[[node]]$left, output)
		output[length(output) + 1] <- nodes[[node]]$value
		output <- inorder(nodes, nodes[[node]]$right, output)
	}
	output
}

nodes <- list()
r <- make_node(nodes, 1, -1, -1); nodes <- r$nodes; n1 <- r$idx
r <- make_node(nodes, 3, -1, -1); nodes <- r$nodes; n3 <- r$idx
r <- make_node(nodes, 2, n1, n3); nodes <- r$nodes; n2 <- r$idx
r <- make_node(nodes, 5, -1, -1); nodes <- r$nodes; n5 <- r$idx
r <- make_node(nodes, 7, -1, -1); nodes <- r$nodes; n7 <- r$idx
r <- make_node(nodes, 6, n5, n7); nodes <- r$nodes; n6 <- r$idx
r <- make_node(nodes, 4, n2, n6); nodes <- r$nodes; root <- r$idx

output <- integer(0)
output <- inorder(nodes, root, output)
cat("[", paste(output, collapse = ", "), "]\n", sep = "")

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

    25output <- integer(0)26output <- inorder(nodes, root, output)
    values this step[]output4(2(1,3),6(5,7))tree

  2. output ← [1]

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(nodes, nodes[[node]]$right, output)
    values this step[] → [1]output

  3. output ← [1, 2]

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(nodes, nodes[[node]]$right, output)
    values this step[1] → [1, 2]output

  4. output ← [1, 2, 3]

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(nodes, nodes[[node]]$right, output)
    values this step[1, 2] → [1, 2, 3]output

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

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(nodes, nodes[[node]]$right, output)
    values this step[1, 2, 3] → [1, 2, 3, 4]output

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

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(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]

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(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]

    9output <- inorder(nodes, nodes[[node]]$left, output)10output[length(output) + 1] <- nodes[[node]]$value11output <- inorder(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]

    26output <- inorder(nodes, root, output)27cat("[", paste(output, collapse = ", "), "]\n", sep = "")
    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

  • R: a tiny named list(value = ..., left = ..., right = ...) per node stored in a plain integer-keyed nodes list arena. The arena pattern keeps the recursion focused on traversal without leaning on reference classes (R5/R6) to fake an object reference graph.
  • The output buffer is a plain integer vector; R's copy-on-modify semantics mean inorder returns the updated output and the caller threads output <- inorder(...) through both child calls — the honest functional spelling of the lesson, with no hidden mutation.
  • The replay shows the running output list and the visited node value on each visit frame, with node(<value>) labels instead of runtime references.