Pre-order Traversal
by Isai Damier, Android Engineer @ Google

  #=====================================================================
  # Author: Isai Damier
  # Title: Pre-order Traversal
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Description: visit node; visit left child; visit right child.
  #    All the left nodes are visited first, effectively.
  #    But a parent is visited before its children.
  #
  # Technical Details:
  #    0] preliminary checks:
  #       1) return if self.root is None;
  #       2) create pointer n
  #    1] create a stack and add self.root to it;
  #    2] while stack is not empty
  #       1) pop stack into n
  #       2) visit n
  #       3) push right child then left child of n to stack
  #        if they are not None.
  #
  # Alternate Algorithm: recursive:
  #
  #     def preorder(self):
  #       _preorder(self.root)
  #
  #
  #     def _preorder(self, n):
  #       if n is not None:
  #         self.visit(n)
  #         _preorder(n.left)
  #         _preorder(n.right)
  #
  #=====================================================================
 
 
from Queue import LifoQueue

class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

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

    n = None
    stack = LifoQueue()
    stack.put( self.root )

    while not stack.empty():
      n = stack.get() # pop last node added
      self.visit( n )
      if n.right is not None:
        stack.put( n.right )
      if n.left is not None:
        stack.put( n.left )

import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #===================================================================
  # Test of preorder method, of class BST.
  #===================================================================
  def testPreorder( 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]

    pre = [200, 100, 50, 25, 35, 75, 150, 125, 175, 300, 250, 225,
                     212, 275, 350, 325, 312, 375, 400]
    expected = ""
    self.assertEquals( expected, result.getvalue() )
    for i in pre:
      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 preorder
    bst.preorder()
    self.assertEquals( expected, result.getvalue() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size
    sys.stdout = old_stdout
    print "done with testPreorder"