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
  #   is asking for level-order traversal. Except, after reading each
  #   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;}
  #
  #     Queue<Node> q =LinkedList<Node>();
  #     q.add(self.root);
  #     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:
      perfectBST.add( i )

    expected = [[50], [25, 75], [12, 40, 62, 87]]

    result = perfectBST.printTreeByLevel()
    self.assertEquals( expected, result )