Preorder Traversal of Binary Tree

Here is the code for iterative preorder traversal of binary trees.

'''class implementing binary tree'''
'''Binary Tree Class and its methods'''
class BinaryTree:
    def __init__(self, root):
        self.root = root #root node
        self.leftChild = None #left child
        self.rightChild = None #right child
     
    #set root node   
    def setRoot(self, root):
        self.root = root
    #get root node    
    def getRoot(self):
        return self.root
    #get left child of a node
    def getLeftChild(self):
        return self.leftChild
    #get right child of a node
    def getRightChild(self):
        return self.rightChild
    #insert a left child of a node
    def insertLeftChild(self, newNode):
        if self.leftChild == None:
            self.leftChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.leftChild = self.leftChild
            self.leftChild = t
    #insert a right child of a node        
    def insertRightChild(self, newNode):
        if self.rightChild == None:
            self.rightChild = BinaryTree(newNode)
        else:
            t = BinaryTree(newNode)
            t.rightChild = self.rightChild
            self.rightChild = t

#recursive function for inorder traversal of binary tree
def preOrderTraversalRecursive(tree):
    if tree == None:
        return 
    else:
        print tree.root
        preOrderTraversal(tree.leftChild)
        preOrderTraversal(tree.rightChild)

#iterative function for inorder traversal of binary tree
def preOrderTraversalIterative(tree)
    stack = []
    if tree == None:
        return
    stack.append(tree)
    while(stack != []):
        
        
        node = stack.pop()
        print node.root
        if node.getRightChild():
            
            stack.append(node.getRightChild())
        
        if node.getLeftChild():
            stack.append(node.getLeftChild())

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 "Preorder traversal of tree recursively is:", preOrderTraversalRecursive(r)
    print "\n\n"
    print "Preorder traversal of the tree iteratively is:", preOrderTraversalIterative(r)
    print "\n\n"

Advertisements