#=====================================================================
# 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"