// D. Scott
// CCI - Problem 4.2
// Generate a binary search tree from an array of sorted integers


public static void main (String[] args)
{
    int[] array = [6,9,13,25,33,42,49,56,78,83,87,90,99,140,157];
    System.out.println("Array of integers:\n" + array);
   // int[] array2 = [5,36,42,81,112,143,177,212];
        
    int root = Math.floor(array.length/2);
    
    int[] indices = new int[array.length];
    
    indices[0] = root;

    // Generate breadth-first index ordering
    boolean doneSplit = false;
    
    int count = 1;
    int count2 = 0;
    for (int i = 1; i < array.length; i++) {
        // Depth level loop
        for (int j = 0; j < i; j++) {
            if (indices[count2] < 2) {
                doneSplit = true;
            }
            if (doneSplit == true)
                break;
            indices[count++] = indices[count2]-(int)((indices[(int)Math.pow(2,i-1)-1]+1)/2);
            indices[count++] = indices[count2]+(int)((indices[(int)Math.pow(2,i-1)-1]+1)/2);
            count2++;
        }
        if (doneSplit == true) {
            for (int k = 0; k < (int)Math.pow(2,i-1); k++) {
                while (count < array.length-1) {
                indices[count++] = indices[count2]-1;
                indices[count++] = indices[count2]+1;
                count2++;
                }
            }
            break;
        }
    }
    
    // print out binary search tree
    System.out.println("\nBinary search tree for array:\n");
    System.out.print("\t\t\t\t\t\t" + array[indices[0]]);  // root
    count = 1;
    for (int i = 0; i < (int)(Math.log(indices.length)/Math.log(2)); i++) {
        // spacing
        System.out.println("\n\n");
        for (int s = 4; s > i; s--)
            System.out.print("\t");
        for (int j = 1; j < Math.pow(2,i+1)+1; j++) {
            if (count < indices.length) {
                System.out.print(array[indices[count++]]);
                if (i == 0)
                    System.out.print("\t\t\t\t");
                else if (i == 1)
                    System.out.print("\t\t");
                else
                    System.out.print("\t    ");
            } else {
                break;
            }
        }
    }
       
    return;
}