unbalanced tree iteration issue

[Ian Kelly]

On Fri, Jan 14, 2011 at 5:15 AM, Alex Boyko <alex.kyrish at gmail.com> wrote:
> So, I'd like to know how should I implement (if it's possible of course)
> __iter__ for my tree class based on recursion without generators?

You could try something like this (untested):

from itertools import chain, imap

...

    def postorder(self, node):
        return chain(chain.from_iterable(imap(self.postorder,
node.childs)), [node])


Or you could write the iterator the old-fashioned way, as an object
with state (also untested):

    def __iter__(self):
        return PostOrderIter(self.root)

class PostOrderIter(object):

    def __iter__(self, node):
        self.stack = [(node, 0)]

    def next(self):
        if not self.stack:
            raise StopIteration
        node, index = self.stack.pop()
        if index < len(node.childs):
            child = node.childs[index]
            self.stack.append((node, index+1))
            self.stack.append((child, 0))
            return self.next()
        else:
            return node