Print left view of the tree

Question

Left view of a Binary Tree is set of nodes visible when tree is visited from left side. Left view of following tree is 12, 10, 25.

       12

    /     \
 10       30
        /    \
      25      40 

Looking for code review, optimizations and best practices. Also verifying space complexity is O(n) and not O(logn) where n is number of nodes in tree.

public class LeftView<T> {

    private TreeNode<T> root;

    /**
     * Takes in a BFS representation of a tree, and converts it into a tree.
     * here the left and right children of nodes are the (2*i + 1) and (2*i + 2)nd
     * positions respectively.
     * 
     * @param items The items to be node values.
     */
    public LeftView(List<? extends T> items) {
        create(items);
    }

    private void create (List<? extends T> items) {
        root = new TreeNode<T>(null, items.get(0), null);

        final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();
        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);
                }
            }
        }
    }

    private static class TreeNode<E> {
        TreeNode<E> left;
        E item;
        TreeNode<E> right;

        TreeNode(TreeNode<E> left, E item, TreeNode<E> right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }


    /**
     * Returns the left view of the binary tree
     * 
     * @return  the left view of binary tree.
     */
    public List<T> leftView() {
        if (root == null) { throw new NoSuchElementException("The root is null"); }

        final List<T> leftView = new ArrayList<T>();
        computeLeftView(root, leftView, 1);
        return leftView;
    }

    private void computeLeftView(TreeNode<T> node, List<T> leftView, int currentDepth) {
        if (node != null) {
            if (currentDepth > leftView.size()) {
                leftView.add(node.item);
            }
            computeLeftView(node.left, leftView, currentDepth + 1);
            computeLeftView(node.right, leftView, currentDepth + 1);
        }
    }


    public static void main(String[] args) {
        final LeftView<Integer> leftView1 = new LeftView<Integer>(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(Arrays.asList(1, 2, 4)  , leftView1.leftView());

        final LeftView<Integer> leftView2 = new LeftView<Integer>(Arrays.asList(1, 2, 3, 4, null, 6, 7));
        assertEquals(Arrays.asList(1, 2, 4)  , leftView2.leftView());

        final LeftView<Integer> leftView3 = new LeftView<Integer>(Arrays.asList(1, 2, 3, null, 5, 6, 7));
        assertEquals(Arrays.asList(1, 2, 5)  , leftView3.leftView());

        final LeftView<Integer> leftView4 = new LeftView<Integer>(Arrays.asList(1, 2, 3, null, null, 6, 7));
        assertEquals(Arrays.asList(1, 2, 6)  , leftView4.leftView());
    }
}

Answer 1

Although the algorithms seems fine, there are issues with the choosen abstractions.

LeftView is a factory of lists, which are left views of an inner tree. LeftView is not a data structure itself, but a factory of it, configured by a list, that are converted to a tree -- too much responsability. Keeping in mind @abuzittin gillifirca advice, a good practise is to refactor factory methods in static, public, methods.

public final class BinaryTrees {
    public static List<T> createLeftViewList(BinaryTree<T> tree) { ... }
}

In your code, LeftView had his own tree representation. To better convey the idea of an algorithm, consider start with simple interfaces, followed by the algorithm itself. That way you get better readability and guarantee further reuse in real code.

public interface BinaryTree<T> {
    BinaryTree<T> left();
    BinaryTree<T> right();
    T element();
}

And than we fill it with runnable code.

public class BinaryTree<T> {
    public BinaryTree<T> left() { return left; }
    public BinaryTree<T> right() { return right; }
    public T element() { return element; }

    private BinaryTree<T> left, right;
    private T element;

    public BinaryTree(List<? extends T> bfsRepresentation) {
        final List<? extends T> items;
        items = new ArrayList<>( bfsRepresentation );
        create( items );
    }
    ...
}

The create method assumes that items is always random access list. Well, it is if we consider only the test methods. If it gets called with a very large LinkedList, you will get quadratic performance.

Consider copying the list in an java.util.ArrayList. An array, T[], should do the trick too, and its preferrable.

Last piece of advice, consider parameterized unit tests in JUnit. There's a good example how to use it in their github wiki.

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in LeftView.create(List<? extends 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.