[Python-ideas] Revised^4 PEP on yield-from

[Antoine Pitrou]

Greg Ewing <greg.ewing at ...> writes:
> 
> > It should be relatively easy to avoid O(n**2) behaviour when traversing
> > a tree,
> 
> How?

By doing the traversal iteratively rather than recursively. Well, I admit
the following function took a couple of attempts to get right:

def traverse_depth_first(tree):
    stack = []
    yield tree.value
    it = iter(tree.children)
    while True:
        try:
            child = it.next()
        except StopIteration:
            if not stack:
                raise
            it, tree = stack.pop()
        else:
            stack.append((it, tree))
            tree = child
            yield tree.value
            it = iter(tree.children)