Morris inorder traversal Morris Inorder traversal - an algorithm for in-order traversal, of a tree, without recursion of extra memory. Looking for code review, optimizations and best practices.

public class MorrisInOrder&lt;T&gt; {

    TreeNode&lt;T&gt; 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 MorrisInOrder(List&lt;? extends T&gt; items) {
        create(items);
    }

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

        final Queue&lt;TreeNode&lt;T&gt;&gt; queue = new LinkedList&lt;TreeNode&lt;T&gt;&gt;();
        queue.add(root);

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

        for (int i = 0; i &lt; half; i++) {
            if (items.get(i) != null) {
                final TreeNode&lt;T&gt; current = queue.poll();                
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

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

    private static class TreeNode&lt;T&gt; {
        TreeNode&lt;T&gt; left;
        T item;
        TreeNode&lt;T&gt; right;

        TreeNode(TreeNode&lt;T&gt; left, T item, TreeNode&lt;T&gt; right) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    /**
     * Returns the inorder traversal of the tree.
     * 
     * @return list containing inorder traversal of elements
     * @throws NoSuchAlgorithmException 
     */
    public List&lt;T&gt; inOrder() throws NoSuchAlgorithmException {
        if (root == null) throw new NoSuchAlgorithmException("The root is null.");

        final List&lt;T&gt; list = new ArrayList&lt;T&gt;();
        TreeNode&lt;T&gt; current  = root;

        while (current != null) {
            if (current.left == null) {
                list.add(current.item);
                current = current.right;
            } else {
                TreeNode&lt;T&gt; predecessor = current.left;
                /*
                 * found the in-order predecessor.
                 */
                while (predecessor.right != null &amp;&amp; predecessor.right != current) {
                    predecessor = predecessor.right;
                }

                if (predecessor.right == null) {
                    // hook it up.
                    predecessor.right = current;
                    current = current.left;
                } else {
                    list.add(current.item);
                    predecessor.right = null;
                    current  = current.right;
                }
            }
        }
        return list;
    }
}


public class MorrisInOrderTest {

    @Test
    public void testBalancedTree() throws NoSuchAlgorithmException {
        final MorrisInOrder&lt;Integer&gt; morrisInOrder1 = new MorrisInOrder&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, 6, 7));
        assertEquals(Arrays.asList(4, 2, 5, 1, 6, 3, 7), morrisInOrder1.inOrder());
    }


    @Test
    public void testUnBalancedTree() throws NoSuchAlgorithmException {
        final MorrisInOrder&lt;Integer&gt; morrisInOrder2 = new MorrisInOrder&lt;Integer&gt;(Arrays.asList(1, 2, 3, 4, 5, null, null));
        assertEquals(Arrays.asList(4, 2, 5, 1, 3), morrisInOrder2.inOrder());
    }
}
private void create (List&lt;? extends T&gt; items) {
    root = new TreeNode&lt;T&gt;(null, items.get(0), null);


This crashes if an empty list is passed in. And since you have this function...

public MorrisInOrder(List&lt;? extends T&gt; items) {
    create(items);
}


It's entirely possible for such a thing to happen.



final int left = 2 * i + 1;
final int right = 2 * i + 2;


right can be set to left + 1 instead.



current  = current.right;


and 

TreeNode&lt;T&gt; current  = root;


There's an extra space in here.



            /*
             * found the in-order predecessor.
             */
            while (predecessor.right != null &amp;&amp; predecessor.right != current) {
                predecessor = predecessor.right;
            }


You're using a block-style comment for single line comment. Why?