Iterate recursion (in a Python Tree)

Question

I've written a Tree class in Python but I'm having issues creating in iterator for it I want to be able to do

phonebook = MyTree()
# Build up tree

for node in phonebook:
    print "%s: %s" % (node.key(), node.data())

But it's not working (says generator object doesn't have key() and data()). My Tree class's __iter__ function returns an iterator class I've created. Here's what I have so far (I know it's wrong and it's not working as it's returning a generator object, since that's what yield does, I want it to remember where it was in the recursion though..so I can't use return) . Basically I just want to return the nodes inorder.

class TreeIterator():
    def __init__(self, root, size):
        self._current = root
        self._size = size
        self.num_visited = 0

    def __iter__(self):
        return self

    def next(self):
        return self._next(self._current)

    def _next(self, curr):
        self.num_visited = self.num_visited + 1
        if self.num_visited == self._size:
            raise StopIteration

        if curr.left is not None and curr.left is not TreeNode.NULL:
            yield self._next(curr.left)

        yield curr

        if curr.right is not None and curr.right is not TreeNode.NULL:
            yield self._next(curr.right)

robert · Accepted Answer · 2010-12-16 17:27:53Z

2

Try changing

if curr.left is not None and curr.left is not TreeNode.NULL:
    yield self._next(curr.left)

yield curr

if curr.right is not None and curr.right is not TreeNode.NULL:
    yield self._next(curr.right)

into

if curr.left is not None and curr.left is not TreeNode.NULL:
    for x in self._next(curr.left):
        yield x

yield curr

if curr.right is not None and curr.right is not TreeNode.NULL:
    for x in self._next(curr.right):
        yield x

It looks like you're yielding an iterator, not a value. I also think your general approach is way too complicated.

self._next(curr.left) returns a generator/iterator. It contains a bunch of values, not just one, so you need to loop through it.

edited Dec 16, 2010 at 17:27

answered Dec 16, 2010 at 16:39

robert

34.6k8 gold badges55 silver badges74 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

robev Over a year ago

This worked, I've seen this before actually but I couldn't get it to work then. Can you explain why this works? I still don't quite understand for x in self_next(curr.left).

Nathan Ernst · Accepted Answer · 2010-12-16 16:40:49Z

1

Looks like you're trying to iterator over the type, not the instance of the type. Change this:

for node in MyTree:
    print "%s: %s" % (node.key(), node.data())

to:

for node in phonebook:
    print "%s: %s" % (node.key(), node.data())

answered Dec 16, 2010 at 16:40

Nathan Ernst

4,62027 silver badges38 bronze badges

1 Comment

robev Over a year ago

Sorry that was a typo, I'm doing #2 :)

Sven Marnach · Accepted Answer · 2010-12-16 16:46:19Z

1

Your function TreeIterator._next() is a generator function. This means it returns an iterator upon being called. So you could store the return value of _next() and call .next() on this return value to get the successive elements of this iterator. What you do on the other hand is always return a newly created iterator in TreeIterator.next(), which is never iterated over. This also explains the error message you get: You iterator is not returning tree entries, but rather new iterators.

I think the easiest fix for this problem is to drop the TreeIterator class completely and copy its ._next() method to the .__iter__() method of your tree class. Maybe a few things need to be fixed, but I don't know your tree class.

edited Dec 16, 2010 at 16:46

answered Dec 16, 2010 at 16:38

Sven Marnach

608k123 gold badges968 silver badges865 bronze badges

2 Comments

robev Over a year ago

Thanks I got rid of the class and all of its attributes (which weren't needed). However it still didn't work, robert's answer fixed the main issue.

Sven Marnach Over a year ago

@robev: Actually both of those were "main issues". You needed to fix both of these bugs to make it work. But glad we could help you :)

Collectives™ on Stack Overflow

Iterate recursion (in a Python Tree)

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

1 Comment

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related