Pre-order Traversalby 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"