An algorithm to create a balanced binary tree from an iterator.

ByConcat.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.function.BinaryOperator;

import static java.util.Arrays.asList;

public class ByConcat {
    /**
     * Given a collection of objects, collapse by evenly weighted binary reduction.
     *
     * <p>This works by appending each item to the stack, and then concatenating the top two items
     * for each 1 in the binary representation of the index.
     *
     * <p>Suppose we want to reduce a list of {@code [a, b, c, d, e, f, g, h]} with simple addition,
     * we would like the resulting expression to be:
     * <pre>((a+b) + (c+d)) + ((e+f) + (g+h))</pre>
     *
     * <p>To understand the algorithm, imagine all those values are 1's, and run the following deskcheck:
     * <table>
     *     <tr><th>Counter</th><th>Stack</th><th>First reduction</th>
     *         <th>Second reduction</th><th>Third reduction</th></tr>
     *     <tr><td>000</td><td>1</td></tr>
     *     <tr><td>001</td><td>1,1</td><td>2</td></tr>
     *     <tr><td>010</td><td>2,1</td></tr>
     *     <tr><td>011</td><td>2,1,1</td><td>2,2</td><td>4</td></tr>
     *     <tr><td>100</td><td>4,1</td></tr>
     *     <tr><td>101</td><td>4,1,1</td><td>4,2</td></tr>
     *     <tr><td>110</td><td>4,2,1</td></tr>
     *     <tr><td>111</td><td>4,2,1,1</td><td>4,2,2</td><td>4,4</td><td>8</td></tr>
     * </table>
     *
     * <p>The key is that the number of reductions is exactly the number of contiguous 1's in the binary counter.
     * @param src The source iterator.
     * @param concat A binary operator that concatenates the values
     * @param empty A default value to return if the source is empty.
     * @param <T> the element type
     * @return the original collection reconstituted as a concatenation
     */
    public static <T> T constructByConcat(Iterator<T> src, BinaryOperator<T> concat, T empty) {
        if (!src.hasNext())
            return empty;
        Deque<T> stack = new ArrayDeque<>();
        int i = 0;
        while (src.hasNext()) {
            // Always append
            stack.addLast(src.next());
            // We want to concat the top of the stack for all the contiguous 1 bits in our index.
            for (int j = i; (j & 1) != 0; j >>= 1) {
                T right = stack.removeLast(), left = stack.removeLast();
                T inter = concat.apply(left, right);
                stack.addLast(inter);
            }
            i++;
        }
        // Collapse the rest of the stack
        while (stack.size() > 1) {
            stack.push(concat.apply(stack.pop(), stack.pop()));
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        System.out.println(constructByConcat(asList(args).iterator(),
                                             (a, b) -> "(" + a + " + " + b + ")", "empty"));
    }
}