use Data::Dumper;
use strict;
use warnings;

my %nodes;
my @children;

while (<>) {
    chomp;
    my ($c,$p)=split "\t";
    push @children,$c unless $nodes{$c};
    $nodes{$_}{name}||=$_
        for $c,$p;
    $nodes{$p}{kids}{$c}=$nodes{$c};
}
delete $nodes{$_}
for @children;
my @roots=keys %nodes;

#print Dumper($nodes{$_}) for @roots;

print_inorder(%nodes);


sub print_inorder {
    my $node= shift;
    print $node->{name}, "\n";
   print_inorder($_)
       for sort { $a->{name} cmp $b->{name} }
    values %{ $node->{kids} || {} };
}
[download]