Laurent_R:

As I mentioned yesterday, seeing what other people do can give you inspiration. Case in point: I just reviewed the solution hdb posted, and got the hint I needed to make mine better: Rather than using just a stack, hdb uses a stack and a reference to the current (sub)tree being worked on. By using the same I idea, I was able to come up with a new version of get_tree_iterator that I like even better:

sub get_tree_iterator {
    my @rtrees=(shift);
    my $tree;
    return sub {
        $tree=pop @rtrees;
        ($tree, $rtrees[@rtrees]) = @$tree while ref $tree;
        return $tree;
    }
}
[download]

This version still descends down the left tree until it hits a leaf, but it uses much less manipulation of the @stack array, and uses the right hand side of the array, which is (I expect) more efficient than the left side. (Editing the right side of the array may cause an expansion of the array, but I'm thinking that expanding the left side of the array may cause unnecessary array copies.)

When I look at this version, I don't feel like I'm missing anything. (Not to say that I'm not--It's amazing how often one can make significant improvements to "optimized" code.)

...roboticus

When your only tool is a hammer, all problems look like your thumb.