Inorder Traversal Of Binary Tree

Although recursion is a very easy way of traversing through Binary Tree but it can easily cause memory problems. The iterative solution can be handy in such cases. A very good explanation of iterative inorder traversal of Binary Tree can be found in the following video produced by Saurabh.

I have implemented using python.

'''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 inOrderTraversalRecursive(tree):
    if tree == None:
        return
    else:
        inOrderTraversal(tree.leftChild)
        print tree.root
        inOrderTraversal(tree.rightChild

#iterative function for inorder traversal of binary tree
def inOrderTraversalIterative(tree)
    current = tree
    stack = []
    done = True
    
    while(done):
        if current:
            stack.append(current)
            current = current.getLeftChild()   
        else:
            if stack == []:
                done = True
            else:
                current = stack.pop()
                print current.root
                current = current.getRightChild()

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

Advertisements