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 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>();
 *     q.add(root);
 *     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>>();

  Queue<Node> q = new LinkedList<Node>();
  q.add(root);
  Node n;

  while (!q.isEmpty()) {
    int size = q.size();
    List<Integer> lvl = new ArrayList<Integer>();
    while (size-- > 0) {
      n = q.remove();//dequeue FIFO
      lvl.add(n.data);
      if (null != n.left) {
        q.add(n.left);
      }
      if (null != n.right) {
        q.add(n.right);
      }
    }
    result.add(lvl);
  }
  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) {
      perfectBST.add(i);
    }
    List<List<Integer>> expected = new ArrayList<List<Integer>>();
    expected.add(Arrays.asList(50));
    expected.add(Arrays.asList(25, 75));
    expected.add(Arrays.asList(12, 40, 62, 87));

    List<List<Integer>> result = perfectBST.printTreeByLevel();
    assertEquals(expected, result);
  }
}