Iterative procedure for a Binary tree post order traversal
Question: I did recursive procedure for binary tree post order traversal in python. This
is the code.

    
    
    from collections import namedtuple
    from sys import stdout
    
    Node = namedtuple('Node', 'data, left, right')
    tree = Node(1,
                Node(2,
                     Node(4,
                          Node(7, None, None),
                          None),
                     Node(5, None, None)),
                Node(3,
                     Node(6,
                          Node(8, None, None),
                          Node(9, None, None)),
                     None))
    
    
    def printwithspace(i):
        stdout.write("%i " % i)
    
    
    def postorder(node, visitor = printwithspace):
    
        if node:
            print "%d-->L"%node.data
            postorder(node.left, visitor)
            print "%d-->R"%node.data
            postorder(node.right, visitor)
            print "Root--%d"%node.data
    
        else:
            print "Null"
    
    stdout.write('\n postorder: ')
    postorder(tree)
    
    stdout.write('\n')
    

Now, I want to do an iterative procedure for binary tree post order traversal
in PYTHON. Can anyone help with this?

Thanks in advance.


Answer: The following code should work. Basically, you do a depth first search with a
stack for the nodes. Additionally, you have a second stack which parallelly
stores whether a node has been expanded already.

    
    
    def postorder_iteratively(node):
        stack = [node]
        expanded = [False]
        while stack:
            while stack and not stack[-1]:          #remove "non-existent" nodes from the top
                stack = stack[:-1]
                expanded = expanded[:-1]
            if stack and not expanded[-1]:          #expand node
                stack += [stack[-1].right, stack[-1].left]
                expanded[-1] = True
                expanded += [False, False]
            elif stack and expanded[-1]:            #if node has been expanded already, print it
                print stack[-1].data
                stack = stack[:-1]
                expanded = expanded[:-1]
    

