BST List from a sorted Array

This is a question from my lab and I am stumped. We basically get an array that is already sorted, and we have to use this array to create a BST in list format. (How does this even look like)? Here is the code that I have thus far, however it doesn’t work at all and I don’t know how to fix it:

    private static void buildBalancedRec(Integer [] tempArr, int start, int end,
        BinarySearchTreeList<Integer> bstList)
{       
    if (bstList.size()<tempArr.length){
        Integer middle  = tempArr[(start+end)/2];
        bstList.add(middle);
        buildBalancedRec(tempArr, start , middle-1 , bstList);
        buildBalancedRec(tempArr, middle+1, end, bstList);
}

Assuming that the array we get is {1,2,3,4,5,6,7}. Start would be 1, and end would be 7. I am assuming the BST list is supposed to look like: {4, 2, 6, 1, 3, 5, 7}, is that correct? The BST would look like:

        4
       / /
      2   6
     //   //
    1 3   5 7

So I assumed what the list would look like from that.

How do I get there? And can I have two lines back-to-back for recursion as I have in my current code?

I tried many ways, however I can never get it to print {4, 2, 6, 1, 3, 5, 7}.

Any guidance would be greatly appreciated!

Note: the method needs to use recursion

Try with:

private static void buildBalancedRec(int[] tempArr, int start, int end, BinarySearchTreeList<Integer> list) {
    if (start < end) {
        int middle = (start + end) / 2;
        list.add(tempArr[middle]);
        buildBalancedRec(tempArr, start, middle, list);
        buildBalancedRec(tempArr, middle + 1, end, list);
    }
}

EDIT:

Full example:

private static void buildBalancedRec(int[] tempArr, int start, int end, List<Integer> list) {
    if (start < end) {
        int middle = (start + end) / 2;
        list.add(tempArr[middle]);
        buildBalancedRec(tempArr, start, middle, list);
        buildBalancedRec(tempArr, middle + 1, end, list);
    }
}

public static void main(String[] args) {
    int[] tempArr = {1, 2, 3, 4, 5, 6, 7};
    List<Integer> list =new ArrayList<>(tempArr.length);
    buildBalancedRec(tempArr, 0, tempArr.length, list);
    System.out.println(list);
}

It prints:

[4, 2, 1, 3, 6, 5, 7]

You could use something similar to the Day Stout Warren method, which converts a tree into a “vine” (like a linked list), then creates a balanced tree from the “vine’, only in this case, the first step would be to convert the sorted array into a “vine”.

https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm

Example code to rebalance a BST. In this case, code is needed to convert a sorted array into a “vine”, then call the function vine_to_tree(). Don’t forget the dummy node that starts the “vine”.

//      rebalance binary search tree

#include <iostream>
#include <iomanip>

struct node {
    size_t value;
    node *p_left;
    node *p_right;
};

node *insert (node *p_tree, size_t value)
{
    if (p_tree == NULL) {
        p_tree = new node;
        p_tree->p_left = NULL;
        p_tree->p_right = NULL;
        p_tree->value = value;
    } else if (value < p_tree->value) {
        p_tree->p_left = insert(p_tree->p_left, value);
    } else {
        p_tree->p_right = insert(p_tree->p_right, value);
    }
    return p_tree;
}

node *delete_tree (node *p_tree)
{
node *p_node;
    while(p_tree != NULL){
        if(p_tree->p_left != NULL) {
            p_node = p_tree->p_left;
            p_tree->p_left = p_node->p_right;
            p_node->p_right = p_tree;
            p_tree = p_node;
        } else {
            p_node = p_tree;
            p_tree = p_tree->p_right;
            std::cout << "deleting " << std::setw(2) << p_node->value << std::endl;
            delete p_node;
        }
    }
    return NULL;
}

//  convert tree to vine (list) of p_rights
node * tree_to_vine(node *p_root, size_t *p_size)
{
node * p_vine_tail;
node * p_remainder;
node * p_temp;
size_t size;

    p_vine_tail = p_root;
    p_remainder = p_vine_tail->p_right;
    size = 0;
    while(p_remainder != NULL){
        if(p_remainder->p_left == NULL){    // if left == null, follow right path
            p_vine_tail = p_remainder;
            p_remainder = p_remainder->p_right;
            size = size + 1;
        } else {                            // else rotate right
            p_temp  = p_remainder->p_left;
            p_remainder->p_left = p_temp->p_right;
            p_temp->p_right = p_remainder;
            p_remainder = p_temp;
            p_vine_tail->p_right = p_temp;
        }
    }
    *p_size = size;
    return p_root;
}

size_t floor_power_of_two(size_t size)
{
size_t n = 1;
    while(n <= size)
        n = n + n;
    return n/2;
}

size_t ceil_power_of_two(size_t size)
{
size_t n = 1;
    while(n < size)
        n = n + n;
    return n;
}

// split vine nodes, placing all even (0, 2, 4, ...) leaves on left branches
// p_root->p_right->p_left = 0, p_root->p_right->p_right->p_left = 2

node * perfect_leaves(node * p_root, size_t leaf_count, size_t size)
{
node *p_scanner;
node *p_leaf;
size_t i;
size_t hole_count;
size_t next_hole;
size_t hole_index;
size_t leaf_positions;

    if(leaf_count == 0)
        return p_root;
    leaf_positions = ceil_power_of_two(size+1)/2;
    hole_count = leaf_positions - leaf_count;
    hole_index = 1;
    next_hole = leaf_positions / hole_count;
    p_scanner = p_root;
    for(i = 1; i < leaf_positions; i += 1){
        if(i == next_hole){
            p_scanner = p_scanner->p_right;
            hole_index = hole_index + 1;
            next_hole = (hole_index * leaf_positions) / hole_count;
        } else {
            p_leaf = p_scanner->p_right;
            p_scanner->p_right = p_leaf->p_right;
            p_scanner = p_scanner->p_right;
            p_scanner->p_left = p_leaf;
            p_leaf->p_right = NULL;
        }
    }
    return p_root;
}

//  left rotate sub-tree
node * compression(node * p_root, size_t count)
{
node *p_scanner;
node *p_child;
size_t i;
    p_scanner = p_root;
    for(i = 1; i <= count; i += 1){
        p_child = p_scanner->p_right;
        p_scanner->p_right = p_child->p_right;
        p_scanner = p_scanner->p_right;
        p_child->p_right = p_scanner->p_left;
        p_scanner->p_left = p_child;
    }
    return p_root;
}

//  convert vine to perfect balanced tree
node * vine_to_tree(node *p_root, size_t size)
{
size_t leaf_count; // # of leaves if not full tree
    leaf_count = size + 1 - floor_power_of_two(size+1);
    perfect_leaves(p_root, leaf_count, size);
    size = size - leaf_count;
    while(size > 1){
        compression(p_root, size / 2);
        size = size / 2;
    }
    return p_root;
}

//  reblance tree to perfect balanced tree
node * rebalance_tree(node *p_root)
{
node * p_pseudo;
size_t size;
    p_pseudo = new node;
    p_pseudo->value = 0;
    p_pseudo->p_left = NULL;
    p_pseudo->p_right = p_root;
    p_pseudo = tree_to_vine(p_pseudo, &size);
    p_pseudo = vine_to_tree(p_pseudo, size);
    p_root = p_pseudo->p_right;
    delete p_pseudo;
    return p_root;
}

int main()
{
node *p_tree = NULL;
size_t i;
    for(i = 0; i < 14; i++)
        p_tree = insert(p_tree, i);
    p_tree = rebalance_tree(p_tree);
    return 0;
}