#=====================================================================
# 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() )
