# 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<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>>();

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);
}
if (right < items.size() && items.get(right) != null) {
current.right = new TreeNode<T>(null, items.get(right), null);
}
}
}
}

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) {
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 {
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());
}
}


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?

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>