Visit Leaves In-order
by Isai Damier, Android Engineer @ Google

  #=====================================================================
  # Author: Isai Damier
  # Title: Visit Leaves In-order
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Statement:
  #   Visit/Print the leaves of this BST in order.
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Alternate Algorithm: recursive:
  #
  #     def leavesInorder(self):
  #       leavesInorder(self.root)
  #
  #     def leavesInorder(self, n):
  #       if n is not None:
  #         leavesInorder(n.left)
  #         if n is None.left and n is None.right: # isLeaf()
  #            self.visit(n)
  #         leavesInorder(n.right)
  #
  #=====================================================================
 
 
from Queue import LifoQueue

class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def leavesInorder( self ):
    stack = LifoQueue()
    n = self.root
    while n is not None or not stack.empty():
      if n is not None:
        stack.put( n )
        n = n.left
      else:
        n = stack.get()
        if n.left is None and n.right is None: # isLeaf()
          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 leavesInorder method, of class BST.
  # draw the tree on paper for visual
  #===================================================================
  def testLeavesInorder( self ):
    bst = BST()
    old_stdout = sys.stdout
    result = sys.stdout = StringIO()

    expected = ""
    self.assertEquals( expected, result.getvalue() )
    expected = "35\n75\n125\n175\n212\n275\n312\n400\n"

    # load data into tree
    treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125,
                      175, 225, 275, 325, 375, 35, 212, 312, 400]
    for i in treeTape:
      bst.add( i )

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

    # test leavesInorder
    result = sys.stdout = StringIO()
    bst.leavesInorder() # prints to standard output
    self.assertEquals( expected, result.getvalue() )
    self.assertEquals( len( treeTape ), bst.size() ) # has correct size
    sys.stdout = old_stdout
    print "done with testLeavesInorder"