Preorder traversal of binary tree to produce formatted string

Question

Given a complete binary tree returns the following format (Parent ( leftchild (leftchild, rightchild), rightchild(leftchild,rightchild) ). Looking for code review, optimizations and best practices.

public final class PreOrderList {

    private TreeNode root;

    /**
     * Constructs a binary tree in order of elements in an array.
     * The input list is treated as  BFS representation of the list.
     * Note that it is the clients responsibility to not modify input list in objects lifetime.
     * 
     */
    PreOrderList(List<String> items) { 
        create (items);
    }

    private static class TreeNode {
        TreeNode left;
        String item;
        TreeNode right;

        TreeNode(TreeNode left, String item, TreeNode right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

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

        final Queue<TreeNode> queue = new LinkedList<TreeNode>();   
        queue.add(root);

        final int half = items.size() / 2;

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;  // http://stackoverflow.com/questions/21156774/unit-testing-complicated-methods-what-to-test-and-what-to-assume

                if (items.get(left) != null) {
                    current.left = new TreeNode(null, items.get(left), null);
                    queue.add(current.left);
                }
                if (right < items.size() && items.get(right) != null) {
                    current.right = new TreeNode(null, items.get(right), null);
                    queue.add(current.right);
                }
            }
        }
    }

    /**
     * Returns the string representation of the format
     * (Parent ( leftchild (leftchild, rightchild), rightchild(leftchild,rightchild) ) 
     * It needs a complete balanced tree, else invalid format is be returned.
     * 
     * @return  the String representation.
     */
    public String getPreorderList() {
        if (root == null) {
            throw new NoSuchElementException("The element cannot be null.");
        }

        final StringBuilder sb = new StringBuilder();
        sb.append("(");
        sb.append(root.item);
        preOrder(root, sb);
        sb.append(")");

        return sb.toString();
    }

    private void preOrder(TreeNode node, StringBuilder sb) {
            if (node.left != null) {
                sb.append("(");
                sb = sb.append(node.left.item);
                preOrder(node.left, sb); 
            }

            if (node.right != null) {
                sb.append(",");
                sb = sb.append(node.right.item + "");
                preOrder(node.right, sb); 
                sb.append(")");
            }
    }


    public static void main(String[] args) {
        PreOrderList pol = new PreOrderList(new ArrayList<String>(Arrays.asList("1", "2", "3", "4", "5", "6", "7")));
        assertEquals("(1(2(4,5),3(6,7)))", pol.getPreorderList());
    }
}

Answer 1

I haven't fully parsed your code, but I would definitely add a check before creating the root. This get(0) would break on an empty list, and would break on a null list. Or you could throw an IllegalArgumentException as well.

Answer 2

You can simplify

PreOrderList pol = new PreOrderList(new ArrayList<String>(Arrays.asList("1", "2", "3", "4", "5", "6", "7")));

to

PreOrderList pol = new PreOrderList(Arrays.asList("1", "2", "3", "4", "5", "6", "7"));

If you take a look at method signature for Arrays.asList you can see it is parameterized by the class of its input. Therefore Arrays.asList("1", "2", "3") knows to return List<String>.

Answer 3

This class should be generalized to allow trees with any type of value to be used. Add a type parameter E to the PreOrderList and TreeNode classes. Your getPreOrderList and preOrder method should be erased entirely; that should be implemented inside the TreeNode class. In fact, there is no need for the PreOrderList class at all; all that behavior could be implemented inside TreeNode:

public class TreeNode<E>{

    public static TreeNode<E> fromIterator(Iterator<E> it){
        if(!it.hasNext()) return null;
        TreeNode<E> root = new TreeNode<E>();
        while(it.hasNext())
            root.add(it.next());
    }
    public static TreeNode<E> fromIterable(Iterable<E> iterable){
        return fromIterator(iterable.iterator());
    }
    public static TreeNode<E> fromArray(E ... array){
        return fromIterable(Arrays.asList(array));
    }


    TreeNode<E> [] children;
    E item;

    private TreeNode(E item, TreeNode ... children) {
        this.children = children;
        this.item = item;
    }

    int childIdx;
    public void add(E item){
        if(children[childIdx] == null)
            children[childIdx] = new TreeNode(item, new TreeNode[children.length]);
        else children[childIdx].add(item);

        childIdx++;
    }

    public boolean contains(Object item){
        if (item==null?this.item==null:item.equals(this.item)) return true;
        for(TreeNode<?> child: children)
            if(child.contains(item)) return true;
        return false;
    }

    @Override
    public String toString(){
        return String.format("%s(%s,%s)",item,left,right);
    }
}