Here's one way to build a nested hash whose structure corresponds to the tree:

my ($level2) = values %$VAR1;

my @work = (my $root = { id => 0 });
while (@work) {
    my @next_work;
    for my $parent (@work) {
        my @children = grep $level2->{$_}{boss} == $parent->{id},
                       keys %$level2;
        $parent->{children} = [ map { id => $_, name => $level2->{$_}{
+name} },
                                @children ];
        push @next_work, @{ $parent->{children} };
        delete @$level2{@children};
    }
    @work = @next_work;
}

use Data::Dumper; print Dumper($root);
[download]