# Post-order Traversalby Isai Damier, Android Engineer @ Google

```  #=====================================================================
# Author: Isai Damier
# Title: Post-order Traversal
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(n).
#
# Description: visit left child; visit right child; visit node.
#
# Technical Details: The iterative implementation of postorder is not
#   as simple as preorder or postorder. Here, the visited nodes must be
#   marked as such; so as not to loop endlessly.
#
#    0] preliminary checks: if self.root is None, return.
#    1] create a stack and push self.root into it.
#    2] create a dictionary to track visited nodes
#    3] while stack is not empty
#       1) peek into stack as n
#       2) if n.left is not None and is not marked as visited
#          THEN add n.left to stack
#       3) ELSE if n.right is not None and is not marked as
#          visited THEN add n.right to stack
#       4)ELSE visit n, mark n  as visited, and pop n from stack
#
#  Alternate Algorithm: recursive:
#
#     def postorder(self):
#       _postorder(self.root)
#
#     def _postorder(self, n):
#       if n is not None:
#         _postorder(n.left)
#         _postorder(n.right)
#         self.visit(n)
#
#=====================================================================

from Queue import LifoQueue

class BST( object ):

def __init__( self ):
self.root = None

def getRoot( self ):
return self.root

def postorder( self ):
if self.root is None:
return

stack = LifoQueue()
stack.put( self.root )
visited = {} # to map Node to Node.data
n = None

while not stack.empty():
n = self.peek( stack )

if n.left is not None and not visited.has_key( n.left.data ):
stack.put( n.left )
elif n.right is not None and not visited.has_key( n.right.data ):
stack.put( n.right )
else:
self.visit( n )
visited[n.data] = n
stack.get() # pop last node added

def peek( self, stack ):
n = stack.queue[stack.qsize() - 1]
return n
```
```import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
#=====================================================================
# Test of postorder method, of class BST.
#=====================================================================
def testPostorder( self ):
bst = BST()
old_stdout = sys.stdout
result = sys.stdout = StringIO()

treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400]
pos = [35, 25, 75, 50, 125, 175, 150, 100, 212, 225, 275, 250,
312, 325, 400, 375, 350, 300, 200]
expected = ""
self.assertEquals( expected, result.getvalue() )
for i in pos:
expected += str( i ) + "\n"