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 {

TreeNode 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 (2i + 1) and (2*i + 2)nd
* positions respectively.
*
* @param items The items to be node values.
*/
public MorrisInOrder(List items) {
create(items);
}

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

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

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

for (int i = 0; i current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

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

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

TreeNode(TreeNode left, T item, TreeNode 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 inOrder() throws NoSuchAlgorithmException {
if (root == null) throw new NoSuchAlgorithmException("The root is null.");

final List list = new ArrayList();
TreeNode current = root;

while (current != null) {
if (current.left == n

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

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

public MorrisInOrder(List 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 current  = root;

There's an extra space in here.

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

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

StackExchange Code Review Q#49252, answer score: 3