BST Size
by Isai Damier

  #=====================================================================
  # Author: Isai Damier
  # Title: Size
  # Project: geekviewpoint
  # Package: algorithms
  #
  # Statement:
  #   Indicate the number of nodes in this BST.
  #
  # Time Complexity of Solution:
  #   Best = Average = Worst = O(n).
  #
  # Technical Details: This function is certainly among the most
  #    doltish methods for tracking the size of a BST: it traverses
  #    the tree each time size is needed. In creating a BST, it is
  #    more sensible to create a size field and track the tree by
  #    incrementing size inside the add function and decrementing
  #    it inside the delete and clear functions. All the same,
  #    writing this function makes for good exercise.
  #
  #=====================================================================
 
 
from Queue import LifoQueue

class BST( object ):

  def __init__( self ):
      self.root = None


  def getRoot( self ):
    return self.root

  def size( self ):
    n = self.root
    size = 0
    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
        size += 1
        n = n.right

    return size;
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
  #=====================================================================
  # Test of size method, of class BST.
  #=====================================================================
  def testSize( self ):
    bst = BST()

    self.assertEquals( 0, bst.size() )
    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() )