Get the levels of a binary tree

Question

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

Answer 1

I think that this code is overly complex for the task on hand. Since you pass in a list that is already tree-like, there is no real reason to convert it into a real tree data structure and then back again. By eliminating the intermediate step, you can reduce overhead and increase speed tremendously.

Level 0 (the top node) starts at element 0
Level 1 starts at element 1
Level 2 starts at element 3
Level 3 starts at element 7
Level 4 starts at element 15
...
Level n starts at element 2^n - 1 and ends at element 2 * (2^n - 1)

Therefore to return any given level: iterate between the indices indicated which can be quickly calculated by some bit-shifting:

start: (2 << n) - 1 end: start << 1

Note: make sure to deal with the nulls while iterating in a desired way.

---

Since you want all the lists use the following code:

// create bounds
int size = items.size();
if (size == 0) return;
List<Integer> bounds = ArrayList<Integer>();
bounds.add(0);
bounds.add(1);
int last = 1;
while (size >= bounds.get(last)) {
 bounds.add(2 * bounds.get(last));
 last++;
}
if (bounds.get(last) != size) {
 bounds.remove(last);
 bounds.add(size);
}
// iterate through
List<List<Integer>> levels = new ArrayList<List<Integer>>();
for (int i = 0; i < bounds.size() - 1; i++) {
 int lower_bound = bounds[i];
 int upper_bound = bounds[i+1];
 List<Integer> level = ArrayList<Integer>();
 for (int j = lower_bound; j < upper_bound; j++) {
 level.add(items.get(j));
 levels.add(level);
return levels;

• JavaDeveloper: this is an interview question - you have to deal in trees
• mleyfman: Well, this code would work as soon as you convert your tree into a flattened list. That is what you were passing your function anyways. If you were passing in a true tree structure (where you only pass the parent node), then that would be a completely different question.
• JavaDeveloper: interviewers would probably say you have a larger space complexity. these things dont matter much in real life but interviews - are based on all tiny optimizations
• mleyfman: If you are talking about creating the bounds array, those could be made programmatically as indicated above (which would make this algorithm utilize only as much space as the tree), but I choose to do it this way to make the loop look nice. The bounds array also only uses log(n) space, which is tiny when compared to the tree.

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in PrintEachLevel.create(List<T> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.