class Tree(object):
    def __init__(self, value, left, right):
        self.value = value
        self.left = left
        self.right = right

    def __iter__(self):
        return TreeIterator(self)

class TreeIterator(object):
    def __init__(self, tree):
        self.stack = [tree]

    def next(self):
        if self.stack:
            tree = self.stack.pop()
            if tree.right is not None:
                self.stack.append(tree.right)
            if tree.left is not None:
                self.stack.append(tree.left)
            return tree.value
        else:
            raise StopIteration

def preorder_generator(tree):
    stack = [tree]
    while stack:
        tree = stack.pop()
        if tree.right is not None:
            stack.append(tree.right)
        if tree.left is not None:
            stack.append(tree.left)
        yield tree.value
    

def preorder(tree):
    if tree is None:
        return
    print tree.value
    preorder(tree.left)
    preorder(tree.right)


def test_iter():
    tree = Tree(1, Tree(2, None, None), Tree(3, Tree(4, None, None), Tree(5, None, None)))
    l = []
    for value in tree:
        l.append(value)
    assert l == [1, 2, 3, 4, 5]


def test_iter_generator():
    tree = Tree(1, Tree(2, None, None), Tree(3, Tree(4, None, None), Tree(5, None, None)))
    l = []
    for value in preorder_generator(tree):
        l.append(value)
    assert l == [1, 2, 3, 4, 5]