Preorder Traversal

Visit the root before each subtree, producing root-left-right order.

Algorithm

The canonical tree is 4(2(1,3),6(5,7)), so this Perl DSA implementation can be compared directly with the rest of the DSA track.

Basic Implementation

basic.pl

use strict;
use warnings;
sub node { my ($value, $left, $right) = @_; return { value => $value, left => $left, right => $right }; }
sub render {
    my ($node) = @_;
    return "_" unless defined $node;
    return "$node->{value}" unless defined $node->{left} || defined $node->{right};
    return "$node->{value}(" . render($node->{left}) . "," . render($node->{right}) . ")";
}
sub sample_tree {
    return node(4, node(2, node(1), node(3)), node(6, node(5), node(7)));
}
sub list_string { return "[" . join(", ", @_) . "]"; }
sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }
my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";

Complexity

Time: O(n)
Space: O(h) recursion stack

Implementation notes

Nodes are Perl hash references with value, left, and right keys, built by node($value, $left, $right).
Node fields are accessed with hash-reference syntax such as $node->{value}, $node->{left}, and $node->{right}.
sample_tree() builds the fixed tree 4(2(1,3),6(5,7)).
my @output is the Perl array that stores traversal values.
preorder(sample_tree(), \@output) passes a reference to that output array, so recursive calls append to the same list.
preorder unpacks ($node, $output) from @_.
The base case is return unless defined $node, so undefined children stop without adding a value.
The visit step is push @$output, $node->{value}; @$output dereferences the output array reference.
The recursive order is fixed in the source: visit current node, recurse left, then recurse right.
The trace records output after each visit: [4], [4, 2], [4, 2, 1], [4, 2, 1, 3], [4, 2, 1, 3, 6], [4, 2, 1, 3, 6, 5], then [4, 2, 1, 3, 6, 5, 7].
list_string(@output) joins the final list with ", ".
print list_string(@output) . "\n" outputs [4, 2, 1, 3, 6, 5, 7].

preorder Preorder records the current node before visiting left and right subtrees.