2
\$\begingroup\$

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());
    }
}
\$\endgroup\$
0

2 Answers 2

3
\$\begingroup\$

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;
\$\endgroup\$
4
  • \$\begingroup\$ this is an interview question - you have to deal in trees \$\endgroup\$ Jul 17, 2014 at 21:47
  • \$\begingroup\$ 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. \$\endgroup\$
    – mleyfman
    Jul 17, 2014 at 21:49
  • \$\begingroup\$ 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 \$\endgroup\$ Jul 17, 2014 at 21:56
  • \$\begingroup\$ 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. \$\endgroup\$
    – mleyfman
    Jul 17, 2014 at 22:04
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.