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

```  #=====================================================================
#  Author: Isai Damier
# Title: In-order Traversal
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(n).
#
# Description: visit left child; visit node; visit right child.
#    This techniques visits a BST in sorted order.
#
# Technical Details:
#    0]preliminary check:
#       1) create stack
#    2] declare n and set it to self.root
#    3] while n is not None or stack is not empty
#       1) if n is not None THEN
#         add n to stack and set n to n.left
#       2) ELSE pop stack into n, visit n, and set n to n.right
#
# Alternate Algorithm: recursive:
#
#     def inorder(self):
#       _inorder(self.root)
#
#     def _inorder(self, n):
#       if n is not None:
#         _inorder(n.left)
#         self.visit(n)
#         _inorder(n.right)
#
#=====================================================================

from Queue import LifoQueue

class BST( object ):

def __init__( self ):
self.root = None

def getRoot( self ):
return self.root

def inorder( self ) :
n = self.root;
stack = LifoQueue()

while n is not None or not stack.empty():
if n is not None:
stack.put( n )
n = n.left
else:
n = stack.get() # pop last node added
self.visit( n )
n = n.right
```
```import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
#=====================================================================
# Test of inorder method, of class BST.
#=====================================================================
def testInorder( self ):
bst = BST()

treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
175, 225, 275, 325, 375, 35, 212, 312, 400]

for i in treeTape:

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

# test levelorder
old_stdout = sys.stdout
new_stdout = sys.stdout = StringIO()
bst.inorder() # assumes visit() prints to screen
treeTape.sort()
result = ( new_stdout.getvalue() ).split()
for i in range( len( treeTape ) ):
if treeTape[i] != int( result[i] ):
self.fail( "inorder traversal self.fails" )

self.assertEquals( len( treeTape ), bst.size() ) # has correct size
sys.stdout = old_stdout
print "done with testInorder"
```