Join/ connect all levels of Binary tree without any aux storage

Question

This program connects all nodes of the binary tree at the same level. A node of a tree contains a left, right and a sibling pointer which would connect it to the next node at the same level. This connection is from left to to right. Example: consider a binary tree with parent as node A and left and right child as node B and C. then this program joins B.sibling to C. If the immediate sibling is null, then it is skipped. More details if needed can be found here. I'm looking for code review, best practices, optimizations etc.

public class JoinLevelsWithoutAuxStore<E> {

    private TreeNode<E> root;

    public JoinLevelsWithoutAuxStore(List<? extends E> items) {
        create(items);
    }

    private static class TreeNode<E> {
        TreeNode<E> left;
        E item;
        TreeNode<E> right;
        TreeNode<E> sibling;

        TreeNode(TreeNode<E> left, E item, TreeNode<E> right, TreeNode<E> sibling) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

    /**
     * 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.
     */
    private void create (List<? extends E> items) {
        root = new TreeNode<E>(null, items.get(0), null, null);

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

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

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode<E> current = queue.poll();                
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

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


    /**
     * Joins the level of the binary tree.
     * If any node is null, it is skipped in the process.
     */
    public void join() {
        if (root == null) throw new IllegalStateException("the root cannot be null");

        TreeNode<E> firstNode = root; 

        while (firstNode != null) {
            TreeNode<E> firstNodeAtNextLevel = null;
            TreeNode<E> prevNodeAtNextLevel = null;
            for (TreeNode<E> currentNode = firstNode; currentNode != null; currentNode = currentNode.sibling) {
                List<TreeNode<E>> nodeList= new ArrayList<TreeNode<E>>();
                nodeList.add(currentNode.left);
                nodeList.add(currentNode.right);

                for (TreeNode<E> node : nodeList) {
                    if (node == null) continue;

                    if (firstNodeAtNextLevel == null) {
                        firstNodeAtNextLevel = node;
                    } else {
                        prevNodeAtNextLevel.sibling = node;
                    }
                    prevNodeAtNextLevel = node;
                }
            }
            firstNode = firstNodeAtNextLevel;
        }
    }

    /**
     * Returns the levelorder representation for the given tree.
     * Each granular item of this iterator is a set of items, 
     * where first element of set is the leftmost non-null item at that level
     * and the last one would be the rightmost non-null item at same level.
     * 
     * A next, advances to next level, and returns the level as a set.
     * 
     * @return  the iterator for levelorder traversal
     */
    public Iterator<List<E>> levelOrderIterator() {
        return new LevelOrderItr();
    }

    private class LevelOrderItr implements Iterator<List<E>> {
        private final Stack<TreeNode<E>> stack;

        public LevelOrderItr() {
            stack = new Stack<TreeNode<E>>();
            stack.add(root);
        }

        @Override
        public boolean hasNext() {
            return !stack.isEmpty();
        }

        @Override
        public List<E> next() {
            if (!hasNext()) throw new NoSuchElementException("No more nodes remain to iterate");

            TreeNode<E> node = stack.pop();           
            if (node.left != null) stack.push(node.left);

            final List<E> levelList = new ArrayList<E>();
            for (TreeNode<E> temp = node; temp != null; temp = temp.sibling) {
                levelList.add(temp.item);
            }
            return levelList;
        }

        @Override
        public void remove() {
            throw new UnsupportedOperationException("Invalid operation for pre-order iterator.");
        }
    }



    public static void main(String[] args) {
        Integer[] arr1 = {1, 2, 3, 4, null, null, 7};
        List<Integer> list1 = new ArrayList<Integer>(Arrays.asList(arr1));

        JoinLevelsWithoutAuxStore<Integer> joinLevels = new JoinLevelsWithoutAuxStore<Integer>(list1);
        joinLevels.join();

        int ctr = 0;
        Iterator<List<Integer>> itr = joinLevels.levelOrderIterator();
        while (itr.hasNext()) {
            List<Integer> list = itr.next();
            System.out.println("Level: " + ctr);
            for (Integer i : list) {
                System.out.print(i + " - ");
            }
            ctr++;
            System.out.println("");
        }
    }
}

Answer 1

My observations:

Use properties - do not expose raw members - your TreeNode implementation exposes raw members. You should use getters and setters instead.

Unused parameters - in your TreeNode constructor you declare 4 parameters, but you always pass only one which is not null (the item), the other parameters are unnecessary.

private static class TreeNode<E> {
    TreeNode<E> left;
    E item;
    TreeNode<E> right;
    TreeNode<E> sibling;

    TreeNode(E item) {
        this.item = item;
    }

    public E getItem() { return item; }

    public TreeNode<E> getLeft() { return left; }
    public void setLeft(TreeNode<E> left) { this.left = left; }

    // ... other getters and setters
}

Unclear algorithm - in your create method you create a half variable, which is half the length of the item list. This suggests you might do something binary (recurse the first half of the list, then the other half, or something like that). Actually, you are going over the list item by item linearly. This creates a very unreadable code, and it took me quite a while to understand what it actually does. If you are iterating over the list - use an Iterator:

private void create (List<? extends E> items) {
    var itemIterator = items.iterator();

    if (!itemIterator.hasNext()) {
      return;
    }
    root = new TreeNode<E>(itemIterator.next());

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

    while (itemIterator.hasNext()) {
        var current = queue.poll();
        var left = itemIterator.next();

        current.setLeft(left);
        queue.add(left);

        if (itemIterator.hasNext()) {
            var right = itemIterator.next();

            current.setRight(right);
            queue.add(right);
        }
    }
}

Your join algorithm is also unclear - you create a list on each iteration, which always contains exactly two elements - left and right - is it a bug?

Meaningful naming - use names which convey the correct meaning - nodeList does not convey what the list is used for, prevNodeAtNextLevel is confusing - since it is used in the current level, not the next...

public void join() {
    if (root == null) throw new IllegalStateException("the root cannot be null");

    TreeNode<E> firstNodeAtNextLevel = root; 

    while (firstNodeAtNextLevel != null) {
        var currentNode = firstNodeAtNextLevel;

        firstNodeAtNextLevel = currentNode.getLeft();

        TreeNode<E> right = null;
        while (currentNode != null) {
            var left = currentNode.getLeft();
            if (right != null) {
                right.setSibling(left);
            }
            right = currentNode.getRight();
            if (left != null) {
                left.setSibling(right);
            }
            currentNode = currentNode.getSibling();
        }
    }
}

Use correct data structures - in LevelOrderItr you manage a Stack, but it never has more than one element! You pop() the current node and push() the next... Simply using TreeNode<E> current; would be sufficient - and more readable

private class LevelOrderItr implements Iterator<List<E>> {
    private final TreeNode<E> current;

    public LevelOrderItr() {
        current = root;
    }

    @Override
    public boolean hasNext() {
        return current != null;
    }

    @Override
    public List<E> next() {
        if (!hasNext()) throw new NoSuchElementException("No more nodes remain to iterate");

        final List<E> levelList = new ArrayList<E>();
        for (TreeNode<E> temp = current; temp != null; temp = temp.sibling) {
            levelList.add(temp.item);
        }
        current = current.getLeft();

        return levelList;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Invalid operation for pre-order iterator.");
    }
}

Answer 2

A minor bug: You get an IndexOutOfBoundsException for an empty list in JoinLevelsWithoutAuxStore.create(List<? extends E> 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.