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

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

Looking for code-review, best practices, and optimizations.

```
public final class SwapTreeLevels implements Iterable {

private TreeNode root;

/**
* Constructs a binary tree in order of elements in an array.
* After the number of nodes in the level have maxed, the next
* element in the array would be a child of leftmost node.
*/
public SwapTreeLevels(List items) {
create(items);
}

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

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

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

for (int i = 0; i current = queue.poll();
final int left = 2 * i + 1;
final int right = 2 * i + 2;

if (items.get(left) != null) {
current.left = new TreeNode(items.get(left));
queue.add(current.left);
}
if (right (items.get(right));
queue.add(current.right);
}
}
}
}

private static class TreeNode {
private TreeNode left;
private T item;
private TreeNode right;

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

/**
* Reverse the alternate levels of the tree.
*/
public void reverseAlternateLevels() {
if (root == null) {
throw new IllegalStateException("The tree is empty.");
}

final List> evenLevelNodes = new ArrayList>();
final List> oddLevelNodes = new ArrayList>();

What is the purpose of the class? Is it intended as a usable data structure or is it only used to reverse the tree levels?

If it's the former, then the name is misleading and should be something akin to AlternateReversibleBinaryTree. If it's the latter then you should not inherit from Iterable as that implies that that the class is a data structure. Right now to me it appears as the class is kind of trying to be both without doing either of them well and violating Singe Responsibility Principle (SRP).

Although I know that Java standard libraries use this pattern of throwing UnsupportedOperationException from immutable object's mutators, it is a actually an anti-pattern as it breaks the Liskov Substitution Principle (LSP). The correct way to solve the problem would have been to use Interface Segregation Principle (ISP). Which is why I generally shy away from the Iterator class and its associates.

As for the algorithm, if the binary tree is handed to you encoded in a list you only need to determine the correct ranges in the list and reverse those without actually building the tree structure. I'll provide an example tomorrow when I'm not falling a sleep if you haven't already figured it out.

Addendum:

Each level \$n=0,1,...\$ of a perfect binary tree has exactly \$2^n\$ nodes. Assume that the tree is packed into an array so that all nodes of level \$n\$ precede all nodes of level \$n+1\$. Also let it be that if node \$i\$ is to the left of node \$j\$ in the tree, then \$i\$ is before \$j\$ in the array. These two constraints specify a canonical mapping of a binary tree into an array.

To reverse all nodes of level \$n>0\$ (as \$n=0\$ is trivially no-op) we need to find the starting index of the level in the array. For zero-based arrays, this can be calculated as \$k=\sum_{i=0}^{n-1}{2^i}\$. The observant reader should note that this is equivalent to \$k=2^n-1\$. So to reverse the nodes, just reverse the order of the elements in the array in the range \$[k, k+2^n]\Leftrightarrow[2^n-1, 2^{n+1}-1]\$.

StackExchange Code Review Q#55850, answer score: 7