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.pl 
use strict; use warnings;

sub make_node {
	my ($nodes_ref, $value, $left, $right) = @_;
	my $idx = scalar @$nodes_ref;
	push @$nodes_ref, { value => $value, left => $left, right => $right };
	return $idx;
}

sub inorder {
	my ($nodes_ref, $node, $output_ref) = @_;
	if ($node != -1) {
		inorder($nodes_ref, $nodes_ref->[$node]->{left}, $output_ref);
		push @$output_ref, $nodes_ref->[$node]->{value};
		inorder($nodes_ref, $nodes_ref->[$node]->{right}, $output_ref);
	}
}

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

my @output = ();
inorder(\@nodes, $root, \@output);
print "[" . join(", ", @output) . "]\n";

Complexity

  • Time: O(n)
  • Space: O(h) call stack

Implementation notes

  • Perl: a hash reference { value => ..., left => ..., right => ... } stored in a plain @nodes arena. The arena pattern keeps the recursion focused on traversal without leaning on recursive blessed references or per-node bless.
  • The output buffer is a plain @output array shared by reference so the push @$output_ref, ... growth is visible to the caller; the lesson does not lean on a generator-style wantarray return value.
  • 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($node->{left}); push @output, $node->{value}; inorder($node->{right})`.
BST invariant The same recursion on a binary search tree always emits values in ascending order.