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 oModified 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>>();
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);
}
}
}
}
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;
evenLevelNodes.add(root);
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>>();
stack.add(root);
}
@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()) {
actual.add(itr.next());
}
assertTrue(expected.equals(actual));
}
}
