# Print BST by Level by Isai Damier, Android Engineer @ Google

```  #=======================================================================
# Author: Isai Damier
# Title: Print BST by Level
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
#   Best = Average = Worst = O(n).
#
# Description:
#   Whenever you hear level-order or breadth-first-search or
#   breadth first traversal, think queue. This problem particularly
#   level, print it as you read in the next level. This is not hard to
#   imagine if you recall that a queue reads with its head and prints
#   with its tail (FIFO): so as you add nodes to the head of the queue,
#   you can simultaneously remove nodes from the tail. Therefore, the
#   gist of the problem is to know how many nodes to print/remove each
#   time.
#
#   As it turns out, it's easy to track levels. The queue always starts
#   with one element, the self.root of the tree, which incidentally is the
#   first level. Then if you remove the self.root and add its children, these
#   children constitute the second level. So let the self.root's level be r.
#   To print the nodes by level, simply
#
#   0] record the size of the queue before adding any children,
#      say x=queue.size(). So level r has x nodes in it.
#   1] as you decrement x down to 0, remove and print the tail node of
#      the queue and add the children of the tail to the queue.
#      When x reaches 0, you will have removed all the nodes at
#      level r and you will have added all their children to the queue;
#      so that the queue would now comprise all the nodes at level r+1.
#
#   If you do really want to print to the console, use the following
#   alternative code. The implemented code however prints the nodes
#   into a list of levels.
#
# Alternative: print to console
#
#   def printByLevel() {
#     if (self.root is None) {return;}
#
#     n;
#
#     while not q.empty()) {
#       int size = q.size();
#       while size-=1 > 0) {
#         n = q.remove() # dequeue FIFO
#         System.out.print(n.data + ", ");
#         if (n.left is not None) {q.add(n.left);}
#         if (n.right is not None) {q.add(n.right);}
#       }
#       System.out.println();
#     }
#   }
#
#=======================================================================

import Queue
class BST( object ):

def __init__( self ):
self.root = None

def printTreeByLevel( self ):
if self.root is None:
return None

result = []

q = Queue.Queue()
q.put( self.root );
n = None

while not q.empty():
size = q.qsize()
lvl = []
while size > 0:
size -= 1
n = q.get() # dequeue FIFO
lvl.append( n.data )
if n.left is not None:
q.put( n.left )

if n.right is not None:
q.put( n.right )

result.append( lvl )

return result
```
```import unittest
from algorithms.BST import BST
from cStringIO import StringIO
import sys
class Test( unittest.TestCase ):

def testPrintTreeByLevel( self ):
perfectBST = BST()

self.assertEquals( 0, perfectBST.height() )
tape = [50, 25, 75, 12, 40, 62, 87]
for i in tape: