One neat perl trick is the ability to push elements onto an array while you iterate over it. Note don't try to do anything but push unless you are feeling *very* lucky. For example you can 'recurse' the file structure with a handful of lines:

sub recurse_tree {
    my @dirs = @_;
    my @files;
    for my $dir ( @dirs ) {
        opendir DIR, $dir or error("Can't open $dir\n");
        while ( my $file = readdir DIR ) {
          next if $file eq '.' or $file eq '..';
          next if -l "$dir/$file";
            push @dirs, "$dir/$file" if -d "$dir/$file";
            push @files, "$dir/$file" if -f "$dir/$file";
        }
        closedir DIR;
    }
  return \@dirs, \@files;
}
[download]

One of the intersting features of this algorithm is that it proceeds width first, rather than depth first as with most recursive algorithms.

Not really. Traversing tree solutions (in any order) tend to be highly-recursive. Of course, any recursive solution can be implemented as an iterative solution, but recursion tends to be more natural for this particular problem.

As for arrayrefs vs. singly-linked list, I would venture that arrayrefs use less memory and will probably be faster. But if you have a working solution and speed/memory is acceptable, you might as well keep what you have.

use Graph::Directed;
use Graph::Base;
use Graph::DFS;

my $g = Graph::Directed->new();

growtree($g, $mydatastruct); # create the tree rooted in $g

my $search = Graph::DFS->new($g); # for the search...

while (my $vertex = $search->next_postorder()){
    my $info = $g->get_attribute('myattrib',$vertex);
    # do stuff with $info...
}

sub growtree{
    my ($g, $mydatastruct) = @_;
    my $data = # ...get stuff from $mydatastruct;
    $g->set_attribute('myattrib',$g, $data);
    my @newedges = # ...get new edges from $mydatastruct
    $g->add_edge($g,$_) for @newedges;
    my @newvertices = grep {! $g->has_vertex($_)} @newedges;
    map { growtree($_,$mydatastruct) } @newvertices;
}
[download]