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_nodealways 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.

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.