C - Generic Binary Search Tree

Question

I'm a novice C programmer (moving onto C++ soon) and I've tried to implement a basic (search,insertion,deletion) generic unbalanced BST whilst adhering to a few OO design principles. I'm looking for some feedback and advice from seasoned C programmers on my code and style.

tree.h

#ifndef TREE_H
#define TREE_H
struct btree_node {
 struct btree_node *left;
 struct btree_node *right;
 void *item;
};
static void btree_free_node(struct btree_node *node);
static struct btree_node* find_min_node(struct btree_node *node);
static struct btree_node* find_max_node(struct btree_node *node);
int btree_search(struct btree_node *root, void *item, int (*comp)(const void*,const void*));
int btree_insert(struct btree_node **root, void *item, unsigned int size, int (*comp)(const void*,const void*));
struct btree_node* btree_delete_node(struct btree_node *root, void *item, unsigned int size, int (*compare_node)(const void*,const void*));
void btree_print(struct btree_node *root, void (*print)(const void *));
void btree_free(struct btree_node *root);
#endif

tree.c

#include "tree.h"
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
int btree_insert(struct btree_node **root, void *item, unsigned int size, int (*compare_node)(const void*,const void*)) {
 // Insert the root 
 if (*root == NULL) {
 *root = malloc(sizeof(struct btree_node));
 if (!(*root)) {
 fprintf(stderr,"malloc() fail\n");
 return 0;
 }
 (*root)->left = (*root)->right = NULL;
 (*root)->item = malloc(size);
 if (!((*root)->item)) {
 fprintf(stderr,"malloc() fail\n");
 free(*root);
 return 0;
 }
 memcpy((*root)->item,item,size);
 } else {
 if (compare_node((*root)->item,item) > 0) {
 //Insert left
 btree_insert(&(*root)->left,item,size,compare_node);
 } else {
 //Insert right
 btree_insert(&(*root)->right,item,size,compare_node);
 }
 }
 return 1;
}
static void btree_free_node(struct btree_node *node) {
 free(node->item);
 free(node);
}
static struct btree_node* find_min_node(struct btree_node *node) {
 node = node->right;
 while (node) node = node->left;
 return node;
}
static struct btree_node* find_max_node(struct btree_node *node) {
 node = node->left;
 while (node) node = node->right;
 return node;
}
struct btree_node* btree_delete_node(struct btree_node *root, void *item, unsigned int size, int (*compare_node)(const void*,const void*)) {
 if (root == NULL) return root;
 else if (compare_node(item,root->item) < 0) root->left = btree_delete_node(root->left,item,size,compare_node);
 else if (compare_node(item,root->item) > 0) root->right = btree_delete_node(root->right,item,size,compare_node);
 else {
 // 1. Deleting a node with two children
 if ( root->left && root->right ) {
 struct btree_node *min_node = find_min_node(root);
 if (!min_node) {
 min_node = find_max_node(root);
 }
 memcpy(root->item,min_node->item,size);
 root->right = btree_delete_node(root->right,min_node->item,size,compare_node);
 } else if (root->left) {
 // 2. Deleting a node with one child (left)
 struct btree_node *node_delete = root;
 root = root->left;
 btree_free_node(node_delete);
 } else if (root->right) {
 // 2. Deleting a node with one child (right)
 struct btree_node *node_delete = root;
 root = root->right;
 btree_free_node(node_delete);
 } else {
 // 3. Deleting a leaf node
 btree_free_node(root); 
 root = NULL;
 }
 }
 return root; 
}
void btree_print(struct btree_node *root, void (*print_node)(const void *)) {
 if (root) {
 print_node(root->item);
 btree_print(root->left,print_node);
 btree_print(root->right,print_node);
 }
}
void btree_free(struct btree_node *root) {
 if (root) {
 free(root->item);
 btree_free(root->left);
 btree_free(root->right);
 free(root);
 }
}
int btree_search(struct btree_node *root, void *item, int (*compare_node)(const void*,const void*)) {
 if (root == NULL) return 0;
 else if (compare_node(item,root->item) > 0) return btree_search(root->right, item, compare_node);
 else if (compare_node(item,root->item) < 0) return btree_search(root->left, item, compare_node);
 else return 1;
}

test.c

#include <stdio.h>
#include "tree.h"
void print_node(const void *node) {
 printf("%d\n",*(int*)node);
}
int compare_node(const void *a, const void *b) {
 return *(int*)a - *(int*)b;
}
int main() {
 struct btree_node *root = NULL;
 for (int i=0; i<10; i++) {
 btree_insert(&root,&i,sizeof(int),compare_node);
 }
 int a = 6;
 printf("found %d ? %d\n",a,btree_search(root, &a, compare_node));
 a = 100;
 printf("found %d ? %d\n",a,btree_search(root, &a, compare_node)); 
 a = 6;
 btree_delete_node(root, &a, sizeof(int),compare_node); 
 printf("found %d ? %d\n",a,btree_search(root, &a, compare_node)); 
 btree_print(root,print_node);
 btree_free(root);
 return 0;
}

To compile and test

gcc test.c tree.c -o test.o -O3

./test.o

found 6 ? 1
found 100 ? 0
found 6 ? 0
0
1
2
3
4
5
7
8
9

Memory leak check with Valgrind

valgrind --leak-check=full --show-leak-kinds=all ./test.o

==91414== HEAP SUMMARY:
==91414== in use at exit: 0 bytes in 0 blocks
==91414== total heap usage: 21 allocs, 21 frees, 1,304 bytes allocated
==91414== 
==91414== All heap blocks were freed -- no leaks are possible

Answer 1

• A bug: btree_insert returns 1 even if a recursive call fails. You shall return exactly what a recursive call returns:

   if (compare_node(....)) {
   return btree_insert(....);
   else {
   return btree_insert(....);
   }
  

  (and return 1; from the successful base case).

• A serious bug: find_min_node and find_max_node always return NULL.

  Notice that your test builds a degenerate tree - no node having 2 children - and hence doesn't exercise those two functions.

• Returning a boolean indicator from btree_search throws away important information. Most likely a caller is interested in the item of a found node, or even the node itself. Consider returning btree_node *. One perk benefit of such approach is that you could call btree_search at the beginning of btree_delete_node.

• As a side note, insert and search in BSTs are naturally iterative. Consider eliminating the recursion.

• Nubcake: Thanks for your suggestions. I went for the recursive solution as it seemed easiest but the recursive insert is quite slow as I've found.

Answer 2

One thing you can do is consolidate the storage of the item and the node itself.

struct btree_node {
 struct btree_node *left;
 struct btree_node *right;
 char item[0];
};
if (!(*root)) {
 fprintf(stderr,"malloc() fail\n");
 return 0;
}
*root = malloc(sizeof(struct btree_node)+size);
memcpy((*root)->item,item,size);

This avoids the second allocation.

• Nubcake: Thanks for your answer. I was unaware such a trick existed in C!