#=====================================================================
# Author: Isai Damier
# Title: Level Order Traversal
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
# Best = Average = Worst = O(n).
#
# Description: visit node; visit cousins; visit children and nephews.
# Level-order (aka breadth-first) traversal visits the elements of a
# binary search tree one level at a time. Imagine a BST as a family
# tree: with siblings and cousins and uncles, etc; level order, then,
# visits the nodes by generation. The grand-parent generation is
# visited first; then the parent generation; then the children
# generation.
#
# Technical Details: Of all the fundamental traversal techniques, level
# order is the only one that uses a queue. All the other techniques
# use a stack, because they are depth-first algorithms. In python
# a LifoQueue may be used to implement a stack.
#
# 0] preliminary checks:
# 1) return if self.root is None
# 2) create queue
# 1] add the self.root to the queue
# 2] while the queue is not empty
# 1) dequeue a node from the queue
# 2) visit the node
# 3) add the children of the node to the queue if they are not None
#
# Application:
# print BST to file then read file back as same BST
#
#=====================================================================
import Queue
class BST( object ):
def __init__( self ):
self.root = None
def getRoot( self ):
return self.root
def levelorder( self ):
if self.root is None:
return
q = Queue.Queue()
q.put( self.root )
n = None
while not q.empty():
n = q.get() # dequeue FIFO
self.visit( n )
if n.left is not None:
q.put( n.left )
if n.right is not None:
q.put( n.right )
import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):
#===================================================================
# Test of levelorder method, of class BST.
#===================================================================
def testLevelorder( self ):
bst = BST()
old_stdout = sys.stdout
result = sys.stdout = StringIO()
treeTape = [200, 100, 300, 50, 150, 250, 350, 25, 75, 125, 175, 225,
275, 325, 375, 35, 212, 312, 400]
# set expectation
expected = ""
self.assertEquals( expected, result.getvalue() )
for i in treeTape:
expected += str( i ) + "\n"
# add elements to tree
for i in treeTape:
bst.add( i )
self.assertEquals( len( treeTape ), bst.size() ) # has correct size
# test levelorder
bst.levelorder() # assumes visit() prints to screen
self.assertEquals( expected, result.getvalue() )
self.assertEquals( len( treeTape ), bst.size() ) # has correct size
sys.stdout = old_stdout
print "done with testLevelorder"