Reverse values of alternate nodes of the tree

Question

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree.

Given tree:

          a

       /     \
      b       c
    /  \     /  \
   d    e    f    g
  / \  / \  / \  / \
  h  i j  k l  m  n  o 

Modified tree:

          a

       /     \
       c       b
     /  \     /  \
    d    e    f    g
   / \  / \  / \  / \
  o  n m  l k  j  i  h 

This question is attributed to GeeksForGeeks. The difference between this and the one solved by me previously here, is that in this case the "values" can be changed rather than the actual nodes. Looking for code review, optmizations and best practices.

public class SwapTreeLevelsValues<T> {

    private TreeNode<T> root;

    public SwapTreeLevelsValues(List<T> nodes) {
        create(nodes);
    }

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

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


    public static class TreeNode<T> {
        private TreeNode<T> left;
        private T item;
        private TreeNode<T> right;

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

    /**
     * Given a perfect binary tree, swaps the even levels.
     * For an non-perfect binary tree, results are unpredictable.
     */
    public void reverseAlternateLevels() {
        if (root == null) {
            throw new IllegalStateException("The root cannot be null"); 
        }
        reverse(root, root, true);
    }


    private void reverse (TreeNode<T> node1, TreeNode<T> node2, boolean level) {
        if (node1 == null) {
            return;
        }

        reverse(node1.left, node2.right, !level);

        if (node1 == root) return;

        if (level) {
            T temp = node1.item; 
            node1.item = node2.item;
            node2.item = temp;
        }


        reverse(node1.right, node2.left, !level);
    }


    @Override
    public int hashCode() {
        return hashCompute(root, 0);
    }

    public int hashCompute (TreeNode<T> node, int item) {
        if (node == null) return item;
        item = 31 * hashCompute (node.left, item) + node.hashCode();
        return hashCompute(node.right, item);
    }


    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        SwapTreeLevelsValues<T> other = (SwapTreeLevelsValues<T>) obj;
        return equal(root, other.root);
    }


    private boolean equal(TreeNode<T> node1, TreeNode<T> node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        if (node1.item != node2.item) {
            return false;
        }

        return equal(node1.left, node2.left) && equal(node1.right, node2.right);
    }
}

public class SwapTreeLevelValuesTest {


    @Test
    public void test() {
        List<Integer> list1 = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31); ;
        List<Integer> list2 = Arrays.asList(1, 2, 3, 7, 6, 5, 4, 8, 9, 10, 11, 12, 13, 14, 15, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16); 
        SwapTreeLevelsValues<Integer> stlv1 = new SwapTreeLevelsValues<>(list1);
        stlv1.reverseAlternateLevels();
        SwapTreeLevelsValues<Integer> stlv2 = new SwapTreeLevelsValues<>(list2);
        System.out.println(stlv2.equals(stlv2));
    }
}

Answer 1

A minor bug: You get an IndexOutOfBoundsException for an empty list in SwapTreeLevelsValues.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.

---

I had to do a double take here:

final int left = 2 * i + 1;
final int right = 2 * i + 2;

It only made sense after looking at the diagram. Still, you're doing a calculation twice... why not do it like this?

final int left = 2 * i + 1;
final int right = left + 1;

That said, you might wanna put a comment there. It's not a trivial line of code.

Looking up a bit...

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

for (int i = 0; i < half; i++) {
    if (items.get(i) != null) {

You're not modifying items. Is it possible for items.get(i) to not return null once it has once returned null? If not, why not break out of the for loop, rather than going through the remaining loops? (Performance when dealing with large TreeMaps).

I can't find anything else, really.