[twic]

> This solution looks extremely similar to the previous one, which is a good thing. Our requirements have experienced a small change (reversing the traversal order) and our solution has responded with a small modification.

Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes. You can make either approach look natural and elegant if you pick the right example.

[aleph_minus_one]

> Now do breadth-first traversal. With the iterative approach, you just replace the stack with a queue. With the recursive approach, you have to make radical changes.

The reason is that no programming language that is in widespread use has first-class support for co-recursion. In a (fictional) programming language that has this support, this is just a change from a recursive call to a co-recursive call.

[Chinjut]

Haskell (I realize this may not pass your threshold for widespread use) has equal support for co-recursion as for structural recursion.

[twic]

Right, you could use co-recursion. Or you could just use a queue.

[naasking]

True, but couldn't you just simulate it by enqueing a thunk/continuation?

[mkbosmans]

No need for radical changes.

  def visit_bf(g):
    n, children = g
    yield n
    if children:
        iterators = [iter(visit_df(c)) for c in children]
        while iterators:
            try:
                yield next(iterators[0])
            except StopIteration:
                iterators.pop(0)
            iterators = iterators[1:] + iterators[:1]

The difference between DFS and BFS is literally just the last line that rotates the list of child trees.

Python is a pretty mainstream language and even though the DFS case can be simplified by using `yield from` and BFS cannot, I consider that just to be syntactic sugar on top of this base implementation.

[_dain_]

Oh wow, I've never seen that "list of iterators" trick before. I always thought you needed an explicit queue for breadth-first.

Thanks!