Level Order Traversal
by Isai Damier, Android Engineer @ Google

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