Inorder traversal of a tree without recursion or stack

Question

Please review the code for code cleanup, smart optimizations and best practices. Also verify my complexity: \$O(n^2)\$, where \$n\$ is the number of nodes.

/**
 * This class traverses the tree and returns in-order representation.
 * This class does not recursion and does not use stack.
 * This code is threadsafe.
 */
public final class TraversalWithoutRecursionWithoutStack<T> {

    private TreeNode<T> root;

     /**
     * Constructs a binary tree in order of elements in an array.
     * The input list is treated as  BFS representation of the list.
     * Note that it is the clients reponsibility to not modify input list in objects lifetime.
     * 
     * http://codereview.stackexchange.com/questions/31334/least-common-ancestor-for-binary-search-tree/31394?noredirect=1#comment51044_31394
     */
    public TraversalWithoutRecursionWithoutStack(List<T> items) {
        create(items);
    }


    /**
     * Idea of inner class is supported by linked list and another code found here:
     * http://stackoverflow.com/questions/5262308/how-do-implement-a-breadth-first-traversal
     * 
     * @author SERVICE-NOW\ameya.patil
     */
    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;
        }
    } 

    private void create (List<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 TreeNode<T> getInorderSuccessor(TreeNode<T> node) {
        assert node != null;

        TreeNode<T> inorderSuccessorCandidate = node.left;
        while (inorderSuccessorCandidate.right != null && inorderSuccessorCandidate.right != node) {
            inorderSuccessorCandidate = inorderSuccessorCandidate.right;
        }
        return inorderSuccessorCandidate;
    }


    /**
     * Returns the list containing items in inorder form.
     * 
     * @returns the list of items in inorder.
     */
    public List<T> inorderTraversal () {
        final List<T> nodes = new ArrayList<T>();
        TreeNode<T> node = root;

        while (node != null) { 

            if (node.left == null) {
                nodes.add(node.item);
                node = node.right;
                continue;
            } 

            final TreeNode<T> inorderSuccessor = getInorderSuccessor(node);

            if (inorderSuccessor.right == null) {
                inorderSuccessor.right = node;
                node = node.left;
            } else {
                inorderSuccessor.right = null;
                nodes.add(node.item);
                node = node.right;
            }
        }

        return nodes; 
    }


    public static void main(String[] args) {
          /**
         *         1
         *       2   3  
         *     4  n  n 7
         */
       Integer[] arr1 = {1, 2, 3, 4, null, null, 7};
       List<Integer> list1 = new ArrayList<Integer>();
       for (Integer i : arr1) {
           list1.add(i);
       }
       TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack1 = new TraversalWithoutRecursionWithoutStack<Integer>(list1);
       System.out.print("Expected: 4 2 1 3 7, Actual: ");
       for (Integer i : traversalWithoutRecursionWithoutStack1.inorderTraversal()) {
           System.out.print(i + " ");
       }

       System.out.println("\n--------------------------------"); 

       /**
        *       1
        *     2   3
        *   4  n 6  n 
        */
       Integer[] arr2 = {1, 2, 3, 4, null, 6};
       List<Integer> list2 = new ArrayList<Integer>();
       for (Integer i : arr2) {
           list2.add(i);
       }
       TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack2 = new TraversalWithoutRecursionWithoutStack<Integer>(list2);
       System.out.print("Expected: 4 2 1 6 3, Actual: ");
       for (Integer i : traversalWithoutRecursionWithoutStack2.inorderTraversal()) {
           System.out.print(i + " ");
       }

       System.out.println("\n---------------------------------");

       /**
        *                         1
        *              /                   \
        *           null                     2
        *         /   \                    /    \
        *     null     null            null       3
        *   /    \      /  \         /   \       /  \
        *  null  null null  null  null   null  null  4
        *   
        */
       Integer[] arr3 = {1, null, 2, null, null, null, 3, null, null, null, null, null, null, null, 4};
       List<Integer> list3 = new ArrayList<Integer>();
       for (Integer i : arr3) {
           list3.add(i);
       }
       TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack3 = new TraversalWithoutRecursionWithoutStack<Integer>(list3);
       System.out.print("Expected: 1 2 3 4, Actual: ");
       for (Integer i : traversalWithoutRecursionWithoutStack3.inorderTraversal()) {
           System.out.print(i + " ");
       }

       System.out.println("\n---------------------------------");

       /**
        *                 4
        *             /     \ 
        *          2          null
        *       /   \        /    \
        *      1    null  null    null
        */
       Integer[] arr4 =  {4, 2, null, 1, null};
       List<Integer> list4 = new ArrayList<Integer>();
       for (Integer i : arr4) {
           list4.add(i);
       }
       TraversalWithoutRecursionWithoutStack<Integer> traversalWithoutRecursionWithoutStack4 = new TraversalWithoutRecursionWithoutStack<Integer>(list4);
       System.out.print("Expected: 1 2 4, Actual: ");
       for (Integer i : traversalWithoutRecursionWithoutStack4.inorderTraversal()) {
           System.out.print(i + " ");
       }
    }
}

Answer 1

I have a few comments on your code and algorithm.

First, I don't understand why you cannot use recursion or a stack. You have not elaborated on this. If it is because this is a learning exercise then perhaps I can understand, but it is a poor example of any normal data-structure manipulation...

If this is a real application then I would have to question the whole thing.... Essentially you are taking a list of Data, and converting it in to a List of data.... there is no apparent manipulation of the data at all (at least from the end-user perspective).

I simply do not see much value in this code.

Still, assuming I am missing something important, what about the actual code? Unfortunately recommending changes while not using a stack or recursion is very challenging.... it's like you have been told to screw two pieces of wood together, but you are not allowed to use a screwdriver.... Ratchet-freak's comment/suggestion to add the parent-node is the right solution... and that fixes a lot, but, without that, there is nothing I feel happy recommending other than some big-picture structural items....

Your class is being treated as the source-data for a loop:

for (Integer i : traversalWithoutRecursionWithoutStack4.inorderTraversal()) {
    ....
}

This implies that your class should be java.lang.Iterable and it is not. If you used this then you can simply:

for (Integer i : traversalWithoutRecursionWithoutStack4) {
    ....
}

As for the data structure, since the code is a 'decorator' for an input list, you should just add the parent-node pointer and be done with it. It is something you know in your create method so there is no extra work. Alternatively, just use stack, or use recursion.

As for the complexity of the algorithm, it is only O(n²) if your input List is an ArrayList or some other O(1) access list. If the input is a LinkedList itself, then your complexity jumps to O(n³). You should find an O(1) way to step through the List in your create() method, probably using an Iterator instead of indexed get(...) lookups. An Iterator over the input is the safest way to do it, but, if you have no choice then in the create() method you should check to see whether the List implements java.util.RandomAccess, and if it does not, then you should copy the input in to an ArrayList, and index-get off the arraylist....

if (! (items instanceof RandomAccess)) {
    items = new ArrayList<>(items);
}

This turns what would be an O(n³) back to one which scales with O(n²) complexity.

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in TraversalWithoutRecursionWithoutStack.create(List<T> items). You don't have a comment stating you need to input a list containing at least something. Consider returning IllegalArgumentException and adding a comment.