public class JoinLevels {

    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 JoinLevels(List<Integer> items) {
        create(items);
    }

    private static class TreeNode {
        TreeNode left;
        int item;
        TreeNode right;
        TreeNode sibling;

        TreeNode(TreeNode left, int item, TreeNode right, TreeNode sibling) {
            this.left = left;
            this.item = item;
            this.right = right;
        }
    }

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

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

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

        for (int i = 0; i < half; i++) {
            if (items.get(i) != null) {
                final TreeNode current = queue.poll();
                final int left = 2 * i + 1;
                final int right = 2 * i + 2;

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




    public void joinWithQueue() {
        if (root == null) return;

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

        int currentLevelNodesCtr = 1;
        int nextLevelNodesCtr = 0;

        TreeNode prev = null;

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            currentLevelNodesCtr--;

            if (node.left != null) { queue.add(node.left); nextLevelNodesCtr++;};
            if (node.right != null) { queue.add(node.right); nextLevelNodesCtr++; };

            if (prev != null) {
                prev.sibling = node;
            }
            prev = node;

            if (currentLevelNodesCtr == 0) {
                prev = null;
                currentLevelNodesCtr = nextLevelNodesCtr;
                nextLevelNodesCtr = 0;
            }
        }
    }



    public void joinWithList() {
        if (root == null) return;
        List<TreeNode> nodeList = new ArrayList<TreeNode>();

        preOrder(root, nodeList, 0);
    }

    private void preOrder (TreeNode node, List<TreeNode> nodeList, int height) {
       if (node == null) return;

       if ((nodeList.size() - 1) >= height) {
           nodeList.get(height).sibling = node;
           nodeList.set(height, node);
       } else {
           nodeList.add(node);
       }

       preOrder(node.left, nodeList, height + 1);
       preOrder(node.right, nodeList, height + 1);
    }

    public void usingNoStorage() {
        if (root == null) return;

        TreeNode firstNodeAtCurrentLevel = root;

        while (firstNodeAtCurrentLevel != null) {

            TreeNode firstNodeAtNextLevel = null;
            TreeNode currentNodeAtNextLevel = null;

            for (TreeNode currentNodeAtCurrentLevel = firstNodeAtCurrentLevel; currentNodeAtCurrentLevel != null; currentNodeAtCurrentLevel = currentNodeAtCurrentLevel.sibling) {

                if (currentNodeAtCurrentLevel.left != null) {
                    if (firstNodeAtNextLevel == null) {
                        firstNodeAtNextLevel = currentNodeAtCurrentLevel.left;
                        currentNodeAtNextLevel = firstNodeAtNextLevel;
                    } else {
                        currentNodeAtNextLevel.sibling = currentNodeAtCurrentLevel.left;
                        currentNodeAtNextLevel = currentNodeAtNextLevel.sibling;
                    }
                }

                if (currentNodeAtCurrentLevel.right != null) {

                    if (firstNodeAtNextLevel == null) {
                        firstNodeAtNextLevel = currentNodeAtCurrentLevel.right;
                        currentNodeAtNextLevel = firstNodeAtNextLevel;
                    } else {
                        currentNodeAtNextLevel.sibling = currentNodeAtCurrentLevel.right;
                        currentNodeAtNextLevel = currentNodeAtNextLevel.sibling;
                    }
                }
            }
            firstNodeAtCurrentLevel = firstNodeAtNextLevel;
            firstNodeAtNextLevel = null;
        }
    }
 }

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

private static final List<Integer> buildList(int[] data) {
    List<Integer> result = new ArrayList<>();
    for (int v : data) {
        result.add(v);
    }
    return result;
}

private static final void printSiblings(String name, int[] reference, JoinLevels jl) {
    List<Integer> result = new ArrayList<>();
    TreeNode node = jl.root;
    while (node != null) {
        result.add(node.item);
        node = node.sibling;
    }
    System.out.printf("%sn   %sn   %sn", name, Arrays.toString(reference), result.toString());
}

public static void main(String[] args) {
    int[][] values = {
            {1, 2, 3, 4, 5, 6, 7, 8, 9},
            {1}
    };

    for (int[] data : values) {
        JoinLevels jllist = new JoinLevels(buildList(data));
        jllist.joinWithList();
        printSiblings("List", data, jllist);
        JoinLevels jlqueue = new JoinLevels(buildList(data));
        jlqueue.joinWithQueue();
        printSiblings("Queue", data, jlqueue);
        JoinLevels jlnone = new JoinLevels(buildList(data));
        jlnone.usingNoStorage();
        printSiblings("None", data, jlnone);
    }
}

List
   [1, 2, 3, 4, 5, 6, 7, 8, 9]
   [1]
Queue
   [1, 2, 3, 4, 5, 6, 7, 8, 9]
   [1]
None
   [1, 2, 3, 4, 5, 6, 7, 8, 9]
   [1]