TRAVERSING IN PREORDER INORDER AND POSTORDER USING STACK : BINARY SEARCH TREE

 ## Compose a non-recursive program, for traversing, a binary tree in preorder, inorder, and postorder?
## Using stack


class Node:
    def __init__(self,data):
        self.data=data
        self.left=None
        self.right=None
        self.visited=False

def Postorder(rootNode):
    nodeStack=[]
    nodeStack.append(rootNode)
    while (not (len(nodeStack)==0)):
        currNode = nodeStack[len(nodeStack)-1]
        if ((currNode.left != None) and (currNode.left.visited == False)):
            nodeStack.append(currNode.left)
        else:
            if ((currNode.right != None) and (currNode.right.visited == False)):
                nodeStack.append(currNode.right)
            else:
                print (currNode.data,end=" ")
                currNode.visited = True
                nodeStack.pop()
    print()

def inOrder(root):
    #set currnet to root of binary tree
    # left -> root -> right
    current=root
    stack=[] # Initialise stack
    done=0
    while True:
        #reach the left most node of the stack
        if current is not None:
            # Please pointer to a tree node on the stack
            # before traversing the node's left subtree
            stack.append(current)
            current=current.left
            #backtrack from the empty subtree and visit the node
            # at the top of the stack; however, if the stack is
            # empty you are done.
        elif stack:
            current=stack.pop()
            print(current.data,end=" ")
            #we have visited the node and its left
            # subtree. now, it's right subtree's turn
            current=current.right    
        else:
            break
    print()    

class newNode():
    def __init__(self,key):
        self.key=key
        #all children are stored in a list
        self.child=[]
#function to traverse tree without recursion
def traverse_tree(root):
    # stack to store the nodes
    nodes=[]                
    # push the current node onto the stack
    nodes.append(root)
    #loop while the stack is not empty
    while(len(nodes)):
        #store the current node and pop it from the stack
        curr=nodes[0]
        nodes.pop(0)

        #current node has been traversed
        print(curr.key,end=" ")
        # store all the children of current node from
        # right to left
        for it in range(len(curr.child)-1,-1,-1):
            nodes.insert(0,curr.child[it])


root=Node(1)
root.left=Node(2)
root.right=Node(3)
root.left.left=Node(4)
root.left.right=Node(5)

print("\nInorder: ")
inOrder(root)

r2=newNode(1)
(r2.child).append(newNode(2))
(r2.child).append(newNode(3))
(r2.child[0].child).append(newNode(4))
(r2.child[0].child).append(newNode(5))
print("\nPreorder:")
traverse_tree(r2)


print("\nPostOrder: ")
Postorder(root)