To add to what's already been written, you can gain some added flexibility when doing depth-first traversal by splitting off the "visiting" into a separate class.

sub traverse {
    my($node, $visitor) = @_;

    $visitor->pre_order($node);
    traverse($node->{left}, $visitor) if defined $node->{left};
    $visitor->in_order($node);
    traverse($node->{right}, $visitor) if defined $node->{right};
    $visitor->post_order($node);
}
[download]

This approach lets the $visitor use any or all of the three types of depth-first traversal.

This approach is rather expensive (in terms of excess method calls), and in terms of stack space, but is still useful on occassion.