If you add sorted data to a binary tree using the conventional binary tree insertion algorithm, the tree will end up as a single rightward-leaning vine, and will perform no better than a sorted linked list.

In order to load sorted data and keep the tree perfectly balanced, it is necessary to add the data in the order in which a binary search would visit it. In other words, the middle element first, then the middle of the left sub-array, the middle of the right sub-array and so on.

Here is an implementation of that algorithm in C:

static void binarytree_load_recursive(btnode ** node, void ** list, size_t size)
{
if (size > 0) {
unsigned int left, right, middle = size / 2;
*node = btnode_create(list[middle]);
left = middle;
right = size - middle - 1;
}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
tree->count = size;
}


As an example, I load a binary tree from a sorted array and then check its height with the algorithm I described in Finding the Height of a Binary Tree Recursively. The height is 2, which is the optimum height for a tree with 7 nodes.

int main(void)
{
char *elements[] = {"A", "B", "C", "D","E","F", "G"};
const unsigned int n = sizeof(elements) / sizeof(const char*);
binarytree *tree;

tree = binarytree_create((cmpfn)strcmp);
printf("Height is %u\n", binarytree_height(tree));
binarytree_for_each(tree, (forfn)puts);
binarytree_delete(tree);

return 0;
}


Output:

Height is 2
A
B
C
D
E
F
G


Here is the rest of the binary tree code:

struct btnode {
struct btnode * left;
struct btnode * right;
void * data;
};
typedef struct btnode btnode;

typedef int(*cmpfn)(const void *, const void *);

struct binarytree {
btnode * root;
cmpfn compare;
unsigned int count;
};
typedef struct binarytree binarytree;

static btnode * btnode_create(void * data)
{
btnode * node = malloc(sizeof(btnode));
if (node) {
node->left = NULL;
node->right = NULL;
node->data = data;
}
return node;
}

binarytree * binarytree_create(cmpfn compare)
{
binarytree * tree = malloc(sizeof(binarytree));
if (tree != NULL) {
tree->root = NULL;
tree->compare = compare;
tree->count = 0;
}
return tree;
}

static void binarytree_clear_recursive(btnode * root)
{
if (root != NULL) {
btnode * left = root->left;
btnode * right = root->right;
free(root);
binarytree_clear_recursive(left);
binarytree_clear_recursive(right);
}
}

void binarytree_clear(binarytree * tree)
{
binarytree_clear_recursive(tree->root);
tree->root = NULL;
tree->count = 0;
}

void binarytree_delete(binarytree * tree)
{
if (tree) {
binarytree_clear(tree);
free(tree);
}
}

typedef void(*forfn)(const void *);

static void binarytree_for_each_recursive(const btnode * root, forfn fun)
{
if (root) {
binarytree_for_each_recursive(root->left, fun);
fun(root->data);
binarytree_for_each_recursive(root->right, fun);
}
}

void binarytree_for_each(const binarytree * tree, forfn fun)
{
binarytree_for_each_recursive(tree->root, fun);
}

static void binarytree_load_recursive(btnode ** node, void ** list, size_t size)
{
if (size > 0) {
unsigned int left, right, middle = size / 2;
*node = btnode_create(list[middle]);
left = middle;
right = size - middle - 1;
}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
tree->count = size;
}

static int max(int a, int b)
{
if (a >= b) {
return a;
}
return b;
}

unsigned int binarytree_height_recursive(const btnode *node)
{
unsigned int height = 0;
if (node->left || node->right) {
height = max(node->left ? binarytree_height_recursive(node->left) : 0,
node->right ? binarytree_height_recursive(node->right) : 0) + 1;
}
return height;
}

unsigned int binarytree_height(const binarytree *tree)
{
unsigned int height = 0;
if (tree->root) {
height = binarytree_height_recursive(tree->root);
}
return height;
}