Bulk loading a binary tree with sorted data

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;
		binarytree_load_recursive(&((*node)->left), list, left);
		binarytree_load_recursive(&((*node)->right), &list[middle + 1], right);
	}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
    binarytree_load_recursive(&(tree->root), list, 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);
	binarytree_load(tree, (void*)elements, n);
    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;
		binarytree_load_recursive(&((*node)->left), list, left);
		binarytree_load_recursive(&((*node)->right), &list[middle + 1], right);
	}
}

void binarytree_load(binarytree * tree, void ** list, size_t size)
{
    binarytree_load_recursive(&(tree->root), list, 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;
}