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.php 
<?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";

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