# Print BST by Levelby 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 root of the tree, which incidentally is the
*   first level. Then if you remove the root and add its children, these
*   children constitute the second level. So let the 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
*
*   public void printByLevel() {
*     if (null == root) {return;}
*
*     Queue<Node> q = new LinkedList<Node>();
*     Node n;
*
*     while (!q.isEmpty()) {
*       int size = q.size();
*       while (size-- > 0) {
*         n = q.remove();//dequeue FIFO
*         System.out.print(n.data + ", ");
*         if (null != n.left) {q.add(n.left);}
*         if (null != n.right) {q.add(n.right);}
*       }
*       System.out.println();
*     }
*   }
*
**********************************************************************/
public List<List<Integer>> printTreeByLevel() {
if (null == root) {
return null;
}

List<List<Integer>> result = new ArrayList<List<Integer>>();

Node n;

while (!q.isEmpty()) {
int size = q.size();
List<Integer> lvl = new ArrayList<Integer>();
while (size-- > 0) {
n = q.remove();//dequeue FIFO
if (null != n.left) {
}
if (null != n.right) {
}
}
}
return result;
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class BSTTest {

@Test
public void printTreeByLevel() {
BST perfectBST = new BST();
assertEquals(0, perfectBST.height());
int[] input = {50, 25, 75, 12, 40, 62, 87};
for (int i : input) {