# Level Order Traversalby 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"