Level Order Traversal of Binary Tree and Reverse Level Order Traversal

class BinaryTree:
    def __init__(self, root):
        self.root = root
        self.leftChild = None
        self.rightChild = None
        
    def setRoot(self, root):
        self.root = root
        
    def getRoot(self):
        return self.root
    
    def getLeftChild(self):
        return self.leftChild
    
    def getRightChild(self):
        return self.rightChild
    
    def insertLeftChild(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
            
    def insertRightChild(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

'''Iterative Level Order Traversal of a Binary Tree'''
def iterativeLevelOrderTraversal(tree):
    current = tree
    queue = []
    queue.append(current)
    while (queue != []):
        temp = queue.pop(0)
        print temp.root
        if temp.getLeftChild():
            queue.append(temp.getLeftChild())
        if temp.getRightChild():
            queue.append(temp.getRightChild())

'''Printing Level Order Traversal in a reverse way'''
def printingLevelOrderReverse(tree):
    stack = []
    if tree == None:
        return 0
    else:
        queue = []
        
        queue.append(tree)
        while(queue != []):
            temp = queue.pop(0)
            stack.append(temp.root)
            if temp.getLeftChild():
                queue.append(temp.getLeftChild())
            if temp.getRightChild():
                queue.append(temp.getRightChild())
                
        if stack != []:
            for i in range(len(stack)):
                print stack.pop()
        else:
            return 0

if __name__ == "__main__":        
        
    r = BinaryTree(5)
    r.insertLeftChild(6)
    r.insertRightChild(7)       
    r.leftChild.insertLeftChild(12)
    r.leftChild.insertRightChild(54)
    r.rightChild.insertRightChild(63)

    print "Levelorder traversal of the tree is:", iterativeLevelOrderTraversal(r)
    print "\n\n"

    print "Printing level order in a reverse way:", printingLevelOrderReverse(r)
    print "\n\n"

Advertisements

One thought on “Level Order Traversal of Binary Tree and Reverse Level Order Traversal

  1. Pingback: Tree Walks and Traversals | codeatsociallywired

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s