Post-order Traversal
by 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"

    # load data into tree
    for i in treeTape:
      bst.add( i )

    self.assertEquals( len( treeTape ), bst.size() ) # has correct size

    # test postorder
    bst.postorder()
    self.assertEquals( expected, result.getvalue() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size
    sys.stdout = old_stdout
    print "done with testPostorder"