#
Level Order Traversal

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