# Get the levels of a binary tree

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

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);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(null, items.get(right), null);
}
}
}
}

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

while (!queue.isEmpty()) {
TreeNode<T> node = queue.poll();

/**
* http://stackoverflow.com/questions/24790507/to-swap-or-create-new-references
*/
if (queue.isEmpty()) {
queue = queueNext;
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<>();
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<>();
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<>();
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<>();
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<>();
assertEquals(listOflist5, bfsTraversal5.getLevels());
}
}


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>();
int last = 1;
while (size >= bounds.get(last)) {
last++;
}
if (bounds.get(last) != size) {
bounds.remove(last);
}

// 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++) {

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.