Given a binary tree, return a list of each level.
I'm looking for a general review and a mention on best-practices, optimization, and verification of my complexities.
Time complexity: \$O(n)\$
Space complexity: \$O(2^{height})\$
public class PrintEachLevel<T> {
private TreeNode<T> root;
public PrintEachLevel(List<T> items) {
create(items);
};
private static class TreeNode<T> {
TreeNode<T> left;
T item;
TreeNode<T> right;
TreeNode(TreeNode<T> left, T item, TreeNode<T> right) {
this.left = left;
this.item = item;
this.right = right;
}
}
private void create (List<T> items) {
root = new TreeNode<T>(null, items.get(0), null);
final Queue<TreeNode<T>> queue = new LinkedList<>();
queue.add(root);
final int half = items.size() / 2;
for (int i = 0; i < half; i++) {
if (items.get(i) != null) {
final TreeNode<T> current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;
if (items.get(left) != null) {
current.left = new TreeNode<T>(null, items.get(left), null);
queue.add(current.left);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(null, items.get(right), null);
queue.add(current.right);
}
}
}
}
public List<List<T>> getLevels() {
if (root == null) {
throw new NullPointerException("The root cannot be null.");
}
List<List<T>> levels = new ArrayList<>();
List<T> level = new ArrayList<>();
Queue<TreeNode<T>> queue = new LinkedList<>();
Queue<TreeNode<T>> queueNext = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
TreeNode<T> node = queue.poll();
level.add(node.item);
if (node.left != null) queueNext.add(node.left);
if (node.right != null) queueNext.add(node.right);
/**
* http://stackoverflow.com/questions/24790507/to-swap-or-create-new-references
*/
if (queue.isEmpty()) {
queue = queueNext;
queueNext = new LinkedList<>();
levels.add(level);
level = new ArrayList<>();
}
}
return levels;
}
}
public class PrintEachLevelTest {
/**
* Simple tree with just 1 node
*/
@Test
public void test1() {
PrintEachLevel<Integer> bfsTraversal1 = new PrintEachLevel<>(Arrays.asList(1));
List<List<Integer>> listOflist1 = new ArrayList<>();
listOflist1.add(Arrays.asList(1));
assertEquals(listOflist1, bfsTraversal1.getLevels());
}
/**
* 10
* / \
* 5 18
* / \ / \
* 4 6 17 19
*/
@Test
public void test2() {
PrintEachLevel<Integer> bfsTraversal2 = new PrintEachLevel<>(Arrays.asList(10, 5, 18, 4, 6, 17, 19));
List<List<Integer>> listOflist2 = new ArrayList<>();
listOflist2.add(Arrays.asList(10));
listOflist2.add(Arrays.asList(5, 18));
listOflist2.add(Arrays.asList(4, 6, 17, 19));
assertEquals(listOflist2, bfsTraversal2.getLevels());
}
/**
* 1
* / \
* null 2
* / \ / \
* null null null 3
*/
@Test
public void test3() {
PrintEachLevel<Integer> bfsTraversal3 = new PrintEachLevel<>(Arrays.asList(1, null, 2, null, null, null, 3));
List<List<Integer>> listOflist3 = new ArrayList<>();
listOflist3.add(Arrays.asList(1));
listOflist3.add(Arrays.asList(2));
listOflist3.add(Arrays.asList(3));
assertEquals(listOflist3, bfsTraversal3.getLevels());
}
/**
* 4
* / \
* 2 null
* / \ / \
* 1 null null null
*/
@Test
public void test4() {
PrintEachLevel<Integer> bfsTraversal4 = new PrintEachLevel<>(Arrays.asList(4, 2, null, 1, null));
List<List<Integer>> listOflist4 = new ArrayList<>();
listOflist4.add(Arrays.asList(4));
listOflist4.add(Arrays.asList(2));
listOflist4.add(Arrays.asList(1));
assertEquals(listOflist4, bfsTraversal4.getLevels());
}
/**
* 1
* 2 3
* 4 null null 7
*
*/
@Test
public void test5() {
PrintEachLevel<Integer> bfsTraversal5 = new PrintEachLevel<>(Arrays.asList(1, 2, 3, 4, null, null, 7));
List<List<Integer>> listOflist5 = new ArrayList<>();
listOflist5.add(Arrays.asList(1));
listOflist5.add(Arrays.asList(2, 3));
listOflist5.add(Arrays.asList(4, 7));
assertEquals(listOflist5, bfsTraversal5.getLevels());
}
}
