#
Print BST by Level

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