In-order Traversal
by Isai Damier

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

    # add elements to tree
    for i in treeTape:
      bst.add( i )

    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"