I am truly flattered. I can show you examples of both DFS and BFS iterators but they are not ones that I converted from a recursive algorithm. I almost never think of problems in terms of recursion. Probably why Haskell still eludes me.

Don't hesitate to /msg me with questions about something I have written, if you would like some examples, or if you would like me to write up a tutorial on something (assuming I am capable).

I am not stuck on doing this recursively - a DFS iterator example or tutorial would be killer. I'll send you a msg, too. Thanks!

perlfan,
Doing a DFS as an iterator is pretty simple. If this code example isn't sufficient, let me know.

#!/usr/bin/perl
use strict;
use warnings;

{
    my %seen;
    my %tree = (
        A => ['B', 'C'], B => ['D', 'E'], C => ['F', 'G'],
        E => ['H', 'I'], G => ['J', 'K'], H => ['L', 'M', 'N'],
        I => ['O', 'P'], K => ['Q'],   
    );

    sub get_root { 'A' }

    sub get_children {
        my ($node) = @_;
        return $tree{$node} ? @{$tree{$node}} : ();
    }

    sub visited {
        my ($node, $val) = @_;
        return $seen{$node} = $val if defined $val;
        return $seen{$node};
    }
}

sub gen_tree_iter {
    my @nodes = get_root();
    return sub {
        {
            my $node = shift @nodes;
            return undef if ! defined $node;
            redo if visited($node);
            visited($node => 1);
            unshift @nodes, get_children($node);
            return $node;
        }
    };
}

my $iter = gen_tree_iter();

while (my $node = $iter->()) {
    print "Visiting $node\n";
}
[download]

Cheers - L~R

perlfan,
I wrote another version of the DFS iterator that was more memory efficient at the sacrifice of speed since I wasn't sure which was more important to you. The most items this version will ever have on the stack/queue is the max depth of the tree.
Read more... (2 kB)

Please let me know if this requires explanation as it is not as clear as the original.

Cheers - L~R