push @{$hash{$child}},$parent;

That doesn't look right. Usually you store a tree the other way round, i.e. for each node you store a list of child nodes. So change that to push @{$hash{$parent}}, $child;, and you'll start to get some results.

This is how I'd traverse the tree:

sub other_walk {
    my ($indent, $item) = @_;
    print ' ' x (2 * $indent);
    print $item, "\n";
    for (@{$hash{$item}}){
        other_walk($indent+1, $_);
    }
}

other_walk(0, 1);
[download]

It's not perfect, but I think it goes into the right direction, and you can add your ASCII art eye candy later on ;-)