level and spiral order traversal

# level order traversal and spiral order traversal of a Tree
class Node(object):
    """
    Representation of a Node in tree
   """
    def __init__(self, value):
        self.value = value
        self.children = []
    def getValue(self):
       return self.value
    def __str__(self):
        return str(self.value)
    def __lt__(self, node):
        return self.value     def __gt__(self, node):
        return self.value > node.value
    def __eq__(self, node):
        return self.value== node.value
class Tree(object):
    """
    Represents a tree with a set of nodes and their children
    We have anotionof tree nodes indexed from left to right
    sequentially
    """
    def __init__(self):
        self.nodes ={}
        self.root = None
    def getRoot(self):
        if self.root is None:
            raise ValueError('Tree isempty')
        return self.root
    def addNode(self, node):
        assert type(node) == Node
        if notself.hasNode(node):
            self.nodes[node] = []
        # assign root if we don't have one    
        if self.root isNone:
            self.root = node
    def addChild(self, p, c):
        assert type(p) == Node and type(c) == Node
        assertself.hasNode(p) and self.hasNode(c)
        if c not in self.getChildren(p):
            self.nodes[p].append(c)
    def getChildren(self, p):
        assert type(p) == Node
        assert self.hasNode(p)
        try:
            returnself.nodes[p]
        except KeyError:
            return []
    def hasNode(self, node):
        assert type(node) ==Node
        return node in self.nodes
        
    def __str__(self):
        for node in self.nodes:
            printnode, ' Children: ',
            for child in self.getChildren(node):
                print child,
            print ''
       return ''
def buildTree():
    t = Tree()
    a = Node(1)
    b = Node(2)
    c = Node(3)
    d =Node(4)
   e = Node(5)
    f = Node(6)
    g = Node(7)
    h = Node(8)
    i = Node(9)
    
    t.addNode(a)
   t.addNode(b)
    t.addNode(c)
    t.addNode(d)
    t.addNode(e)
    t.addNode(f)
    t.addNode(g)
   t.addNode(h)
    t.addNode(i)
    t.addChild(a, b)
    t.addChild(a, c)
    t.addChild(b, d)
    t.addChild(b,e)
   t.addChild(d, f)
    t.addChild(d, g)
    t.addChild(f, h)
    t.addChild(f, i)
    return t
def spiralOrderTraversal():
    t = buildTree()
    # BFS is a level order traversal algorithm
    queue = []
    try: #start with root
        queue.append(t.getRoot())
    except ValueError:
        return # tree is empty
    # reverse, if truereverse children before queueing
    # for spiral order traversing
    reverse = False
    while len(queue) > 0:
        # Letsvisit all the nodes in the queue to complete a level
        children = []
        while len(queue) > 0:
            node = queue.pop(0)# by default pop returns last element
            print 'Visting node ', node
            # get all the children ofnode
            for c in t.getChildren(node):
                children.append(c)
        if reverse:
           children.reverse()
            reverse = False
        else:
            reverse = True
        for c inchildren:
            # add all the children to BFS queue
            queue.append(c)
def levelOrderTraversal():
    t =buildTree()
    # BFS is a level order traversal algorithm
    queue = []
    try:
        queue.append(t.getRoot())
   except ValueError:
        return # tree is empty
    while len(queue) > 0:
        node = queue.pop(0) # by defalut pop returns lastelement
        print 'Visting node ', node
        # add all the children to BFS queue
        for c int.getChildren(node):
            queue.append(c)
spiralOrderTraversal()