I'd be tempted to use recursion. Something like (semi-pseudo only I'm afraid - haven't got time to write real code - I'm at work :)...

my $tree = build_tree(0);
print_tree($tree);
.
.
sub build_tree {
    my $index = shift();
    my %tree;
    foreach ("select id from table where cat_id = $index") {
       %tree{$_} = build_tree($_) || $_;
   }
   \%tree;
}
.
etc.
[download]

Hope all of this helps.