Balancing a Binary Tree

[timb89]

I need to balance a binary tree which is in an array.

void balance(int lower, int upper)
{ 
    int middle = (lower + upper)/2;
    
    cout << a[middle] << endl;
    
    if (middle!=lower)
       balance(lower, middle-1);
    
    if (middle!=upper)
       balance(middle+1, upper);
}

I've created the shell of the function just to get the idea doing the right thing. I'm not get the correct output i was 100% expecting.

1 2 3 4 5 6 7 8 9, is giving me:

5 2 1 3 4 8 6 7 9 0

Can anyone give me some help in regards to fixing this and creating a balanced binary tree.

Thanks!