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.R 
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 = "")

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