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

Antoine Pitrou solipsis at pitrou.net
Thu Feb 19 23:54:02 CET 2009

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:
            child = it.next()
        except StopIteration:
            if not stack:
            it, tree = stack.pop()
            stack.append((it, tree))
            tree = child
            yield tree.value
            it = iter(tree.children)

More information about the Python-ideas mailing list