4
\$\begingroup\$

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

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

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>

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