Taking kcott and Laurent_R's suggestions, I changed my traverse function to look like this:

sub traverse {
    my $tree = shift;
    return unless defined $$tree->{left} and defined  $$tree->{right};
    traverse(\$tree->{left});
    print $$tree->{val};
    print "\n";
    traverse(\$tree->{right});
}
[download]

The code runs fine, but there is no output. I guess I made a very basic mistake in the insert function but I can't figure it out. Can someone point me to an implementation of binary tree in Perl? I do not intend to use the Tree::Binary module.