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.

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.