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

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>>();

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

/**
* 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>>();

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>>();
}

@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) {
}
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("");
}
}
}

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>>();

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

current.setLeft(left);

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

current.setRight(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) {
}
current = current.getLeft();

return levelList;
}

@Override
public void remove() {
throw new UnsupportedOperationException("Invalid operation for pre-order iterator.");
}
}
• Overall a very meaningful feedback, except first point "Use properties - do not expose raw members" the class is a private nested class, and its OK to not do the getter / setter stuff as these classes are confined to the outer class. Its similar to Entry/Node of linkedlist. Commented Feb 18, 2014 at 20:28
• I can see your point (although there is no harm in encapsulating private classes), you might consider though, to make E item final, since it is not supposed to change after instanciation, and that cannot be conveyed otherwise when the member is exposed. Commented Feb 18, 2014 at 20:41
• Agree on this here. Commented Feb 18, 2014 at 20:43

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.