Morris inorder traversal

Question

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<T> {
 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 MorrisInOrder(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<T> {
 TreeNode<T> left;
 T item;
 TreeNode<T> right;
 TreeNode(TreeNode<T> left, T item, TreeNode<T> 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<T> inOrder() throws NoSuchAlgorithmException {
 if (root == null) throw new NoSuchAlgorithmException("The root is null.");
 final List<T> list = new ArrayList<T>();
 TreeNode<T> current = root;
 while (current != null) {
 if (current.left == null) {
 list.add(current.item);
 current = current.right;
 } else {
 TreeNode<T> predecessor = current.left;
 /*
 * found the in-order predecessor.
 */
 while (predecessor.right != null && 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<Integer> morrisInOrder1 = new MorrisInOrder<Integer>(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<Integer> morrisInOrder2 = new MorrisInOrder<Integer>(Arrays.asList(1, 2, 3, 4, 5, null, null));
 assertEquals(Arrays.asList(4, 2, 5, 1, 3), morrisInOrder2.inOrder());
 }
}

Answer 1

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

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

public MorrisInOrder(List<? extends T> 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<T> 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?

Answer 2

In addition to Pimgd's remarks I want to throw in:

Program against high Interfaces, not low ones:

Currently your methods all take a List<? extends T>. That in itself is quite nice already. Now a traversal of existing elements does not necessarily have to be done on an ordered Collection only.

I suggest you explore the possiblities of passing int Collection<? extends T> or even higher: Iterable<? extends T>