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

Basic Implementation

basic.php
Replay: real traced execution (multi-file project)
<?php
function make_node(&$nodes, $value, $left, $right) {
	$idx = count($nodes);
	$nodes[] = ["value" => $value, "left" => $left, "right" => $right];
	return $idx;
}

function inorder(&$nodes, $node, &$output) {
	if ($node != -1) {
		inorder($nodes, $nodes[$node]["left"], $output);
		$output[] = $nodes[$node]["value"];
		inorder($nodes, $nodes[$node]["right"], $output);
	}
}

$nodes = [];
$n1 = make_node($nodes, 1, -1, -1);
$n3 = make_node($nodes, 3, -1, -1);
$n2 = make_node($nodes, 2, $n1, $n3);
$n5 = make_node($nodes, 5, -1, -1);
$n7 = make_node($nodes, 7, -1, -1);
$n6 = make_node($nodes, 6, $n5, $n7);
$root = make_node($nodes, 4, $n2, $n6);

$output = [];
inorder($nodes, $root, $output);
echo "[" . implode(", ", $output) . "]\n";

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

    25$output = [];26inorder($nodes, $root, $output);
    values this step[]$output4(2(1,3),6(5,7))tree

  2. $output ← [1]

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($nodes, $nodes[$node]["right"], $output);
    values this step[] → [1]$output

  3. $output ← [1, 2]

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($nodes, $nodes[$node]["right"], $output);
    values this step[1] → [1, 2]$output

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

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($nodes, $nodes[$node]["right"], $output);
    values this step[1, 2] → [1, 2, 3]$output

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

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($nodes, $nodes[$node]["right"], $output);
    values this step[1, 2, 3] → [1, 2, 3, 4]$output

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

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($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]

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($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]

    10inorder($nodes, $nodes[$node]["left"], $output);11$output[] = $nodes[$node]["value"];12inorder($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]

    26inorder($nodes, $root, $output);27echo "[" . implode(", ", $output) . "]\n";
    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

  • PHP: a tiny associative-array node ["value" => ..., "left" => ..., "right" => ...] stored in a plain indexed-array $nodes arena. The arena pattern keeps the recursion focused on traversal without leaning on object reference graphs through a class TreeNode.
  • The output buffer is a plain array passed by reference so $output[] = ... growth is visible to the caller; the lesson does not lean on a sequence helper like array_map or generators.
  • The replay shows the running $output list and the visited node value on each visit frame, with node(<value>) labels instead of runtime references.