# 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<T> implements Iterable<T> {

private TreeNode<T> 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<T> items) {
create(items);
}

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

final Queue<TreeNode<T>> queue = new LinkedList<TreeNode<T>>();

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

private static class TreeNode<T> {
private TreeNode<T> left;
private T item;
private TreeNode<T> 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<TreeNode<T>> evenLevelNodes = new ArrayList<TreeNode<T>>();
final List<TreeNode<T>> oddLevelNodes = new ArrayList<TreeNode<T>>();

int currentLevel = 0;

while (evenLevelNodes.size() != 0 || oddLevelNodes.size() != 0) {
if (currentLevel % 2 == 0) {
if (populateOddLevel(evenLevelNodes, oddLevelNodes))
hook(evenLevelNodes, oddLevelNodes);
evenLevelNodes.clear();
} else {
if (populateEvenLevel(oddLevelNodes, evenLevelNodes))
hook(oddLevelNodes, evenLevelNodes);
oddLevelNodes.clear();
}
currentLevel++;
}
}

/**
* Returns true empty list can be populated, else false.
*/
private boolean populateOddLevel(List<TreeNode<T>> listFull, List<TreeNode<T>> listEmpty) {
for (int i = listFull.size() - 1 ;  i >= 0 ; i--) {
// reversed the odd level, since right is populated before left.
final TreeNode<T> node = listFull.get(i);
if (node.right != null) { listEmpty.add(node.right); }
if (node.left != null)  { listEmpty.add(node.left); }
}
return listEmpty.size() > 0;
}

/**
* Returns true if the empty list is populated, else false.
*/
private boolean populateEvenLevel(List<TreeNode<T>> listFull, List<TreeNode<T>> listEmpty) {
for (int i = listFull.size() - 1 ;  i >= 0 ; i--) {
// even levels not reversed, since left is populated before right.
final TreeNode<T> node = listFull.get(i);
if (node.left != null)  { listEmpty.add(node.left); }
if (node.right != null) { listEmpty.add(node.right); }
}
return listEmpty.size() > 0;
}

private void hook(List<TreeNode<T>> source, List<TreeNode<T>> target) {
for (int i = 0; i < source.size(); i++) {
source.get(i).left = target.get(2 * i);
source.get(i).right = target.get(2  * i + 1);
}
}

/**
* Returns the preorder representation for the given tree.
*
* @return  the iterator for preorder traversal
*/
@Override
public Iterator<T> iterator () {
return new PreOrderItr();
}

private class PreOrderItr implements Iterator<T> {
private final Stack<TreeNode<T>> stack;

public PreOrderItr() {
stack = new Stack<TreeNode<T>>();
}

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

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

final TreeNode<T> node = stack.pop();

if (node.right != null) stack.push(node.right);
if (node.left != null) stack.push(node.left);

return node.item;
}

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

}

public class SwapTreeLevelTest {

@Test
public void test ( ) {
Integer[] a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
SwapTreeLevels<Integer> swaplevel = new SwapTreeLevels<Integer>(Arrays.asList(a));

swaplevel.reverseAlternateLevels();

List<Integer> expected =  Arrays.asList(1,3, 4, 15, 14, 5, 13, 12, 2, 6, 11, 10, 7, 9, 8);
List<Integer> actual = new ArrayList<Integer>();

Iterator<Integer> itr = swaplevel.iterator();
while (itr.hasNext()) {
}

assertTrue(expected.equals(actual));
}

}


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.

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

## Documentation

The first thing that comes to my mind is your doc sentences like this one:

Constructs a binary tree in order of elements in an array.

Rather than an array, I'd be more specific and use the specified array or the given array. Also, the parameter is a List, not an array.

Note: Yes, I'm a Javadoc maniac =)

## Algorithm

Was it mandatory to represent your data in a true tree ?

I feel like the array representation would be much simpler (no need to bother with subtrees). Also, you almost get your input as an array already. What's more, what you end up doing is storing your levels back into lists.

Why not just split the original list, reverse the alternate sublists, then concatenate them back together ? This way, no need to hook them, etc.

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