#
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 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); } }