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"
Pingback: Tree Walks and Traversals | codeatsociallywired