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

Feb. 19, 2009


      Greg Ewing <greg.ewing@...> 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)

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

Antoine Pitrou