1
\$\begingroup\$

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

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.

\$\endgroup\$
2
\$\begingroup\$

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>.

\$\endgroup\$
2
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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