Trees

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.

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

Basic Implementation

basic.pl
Replay: real traced execution (multi-file project)
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";

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

    1use strict;2use warnings;
    values this step4(2(1,3),6(5,7))tree[]output

  2. output ← [4]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[] → [4]output4node

  3. output ← [4, 2]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4] → [4, 2]output2node

  4. output ← [4, 2, 1]

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2] → [4, 2, 1]output1node

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

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2, 1] → [4, 2, 1, 3]output3node

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

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2, 1, 3] → [4, 2, 1, 3, 6]output6node

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

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2, 1, 3, 6] → [4, 2, 1, 3, 6, 5]output5node

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

    13sub list_string { return "[" . join(", ", @_) . "]"; }14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2, 1, 3, 6, 5] → [4, 2, 1, 3, 6, 5, 7]output7node

  9. my @output; preorder(sample_tree(), \@output); print list_string(@outp…

    14sub preorder { my ($node, $output) = @_; return unless defined $node; push @$output, $node->{value}; preorder($node->{left}, $output); preorder($node->{right}, $output); }15my @output; preorder(sample_tree(), \@output); print list_string(@output) . "\n";
    values this step[4, 2, 1, 3, 6, 5, 7]output

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