How to make a class iterable, but not have the iterator modified if you modify the class?

Question

I am new to python and to coding in general, so I'm very lost. I have coded a "Node" class (shown below at the very bottom) that instantiates a binary search tree and a couple of methods like insert(), and elements() (which returns a list of the elements by inorder transversing the tree). I am supposed to make this class iterable: "iter__(self) should return a NodeIterator, which returns elements from the tree in sorted order. Modifying the tree should not modify existing iterators." I'm trying to do this by inserting this code into the class right now:

 def __iter__(self):
    x=self.copy()
    x.i=0
    return x

def next(self):
    lst=x.elements()
    #??? No idea what to do from here.  

I defined x=self.copy() to try to cover the fact that modifying the tree shouldn't modify the iterator, but I don't know if that is the right idea. Here is my Node class with a decorator used in one of my methods:

def depth(old_f):
''' Write a decorator that overrides the standard behavior of
a function that returns True or False and instead returns
0 for False or n for number of recursive calls needed to
return True.
'''
    def new_f(*args):
        res = old_f(*args)
        if res is True:
            return 1
        elif res:
            return 1 + res
        else:
            return 0
    return new_f


Class Node(object):
'''
Modify your Node class from homework 4 as follows:

Two elements that compare equal shouldn't be allowed in the Tree. If a
copy is inserted, throw an AlreadyExistsException with the error
message "Element [x] is already in the tree".

__iter__(self) should return a NodeIterator, which returns elements from
the tree in sorted order. Modifying the tree should not modify
existing iterators.
'''
count = 0

def __init__(self, val, left=None, right=None):
    self.Val = val
    self.Left = left
    self.Right = right
    Node.count += 1

def __repr__(self):
    '''If the node has neither a left nor right child,
    simply return Node(val). Else, return Node(x, val, y),
    where x and y are recursive calls that return the
    left and right children, respectively.
    '''
    if self.Left is None and self.Right is None:
        return "Node({})".format(self.Val)
    else:
        return "Node({}, {}, {})".format(self.Left, self.Val, self.Right)

@depth
def search(self, element):
    ''' Finds whether a given element is in the tree.
    Returns True if the element is found, else returns False.

    Give it the depth decorator you defined earlier.
    '''
    if element == self.Val:
        return True
    elif self.Val > element and self.Left is not None:
        return self.Left.search(element)
    elif self.Val < element and self.Right is not None:
        return self.Right.search(element)
    else:
        return False

def insert(self, element):
    ''' Insert an element into a binary search tree rooted
    at this Node. After insertion, return the modified node.

    Our implementation will allow duplicate nodes. The left subtree
    should contain all elements <= to the current element, and the
    right subtree will contain all elements > the current element.
    '''
    if element <= self.Val:
        if self.Left is not None:
            self.Left.insert(element)
        else:
            self.Left = Node(element)
    else:
        if self.Right is not None:
            self.Right.insert(element)
        else:
            self.Right = Node(element)
    return self

def elements(self):
    ''' Return a list of the elements visited in an inorder traversal:
    http://en.wikipedia.org/wiki/Tree_traversal
    Note that this should be the sorted order if you've inserted all
    elements using your previously defined insert function.
    '''
    if self.Left is None and self.Right is None:
        return [self.Val]
    elif self.Left is None and self.Right is not None:
        return [self.Val] + self.Right.elements()
    elif self.Left is not None and self.Right is None:
        return self.Left.elements() + [self.Val]
    else:
        return self.Left.elements() + [self.Val] + self.Right.elements()

Answer 1

Don't define next on the class; that makes the instances iterators (which necessarily iterate the object directly) when what you want is to have an iterable that is not an iterator. To do that, you define __iter__ and have it return a whole new iterator over a copy of your object.

Since you've already got an elements method that effectively snapshots your Node, it's not hard to use that to make a snapshotting iterator; there's is no point in copying the structure because you're just iterating in order anyway, and elements can do the work for you (and use less memory on the snapshot to boot). Normally, I'd just make __iter__ a generator function, e.g.:

 def __iter__(self):
     # Python 3 simple version
     yield from self.elements()
     # Python 2 or 3 version
     for x in self.elements():
         yield x

But since your assignment calls for a special NodeIterator class, that won't do. For that, you need to make a new class (possibly defined inside your existing Node class to namespace it):

class Node(object):
    ...
    class NodeIterator(object):
        def __init__(self, node):
            self.it = iter(node.elements())

        def __iter__(self):
            return self

        def next(self):
            return next(self.it)
        __next__ = next  # Makes code work on Py2 and Py3 without modification

    def __iter__(self):
        return NodeIterator(self)

You can see why I wouldn't normally bother with a special class when generator functions for __iter__ (functions using the yield magic) are so much simpler, but that's the basic structure. You can read more about iterators on the Python wiki, or about the basic interfaces on the Python collections ABC documentation.