Binary Trees in C

Question

I have the following code:

struct treenode;
typedef struct treenode* TreeNode;
struct treenode {
void* data;
TreeNode left, right;
};

TreeNode newTreeNode(void* data){
    TreeNode node = (TreeNode) malloc(sizeof(struct treenode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

bool insert(TreeNode tree, TreeNode node, int (*comp)(void*, void*)){
if(tree == NULL){
    tree = node;
    return true;
}
if(comp(node->data, tree->data) == 0){
    return false;
}
else if (comp(node->data, tree->data) < 0){
    insert((tree->left), node, comp);
}
else {
    insert((tree->right), node, comp);
}
return false;
}

int compare(void* i, void* j) {
if (*(int*)i < *(int*)j)
    return -1;
else if (*(int*)i == *(int*)j)
    return 0;
else
    return 1;
}

It works fine for 3 nodes, but when I try to insert more it doesn't get past the first line of the tree (the line after the root) because it doesn't seem to have updated the root node. I think it's something to do with the pointers in my insert method, but I've tried everything I can think of and I'm still getting nowhere.

Any help is much appreciated.

Answer 1

bool insert(TreeNode tree, TreeNode node, int (*comp)(void*, void*)){
if(tree == NULL){
    tree = node;
    return true;
}

The problem (or at least a problem) is right here: you're passing in tree as a pointer to a treenode, then you assign node to that pointer -- but you're only assigning to the local copy of the pointer, which doesn't affect the pointer outside that function. To accomplish something, you'd want something like:

bool insert(TreeNode *tree, TreeNode node, int (*comp)(void *, void *)) { 
    if (*tree == NULL) {
        *tree = node;
        return true;
    }
// ....

This way, you're changing the pointer whose address was passed into the function.

Alternatively, you might consider always putting a single node into the tree immediately upon creation, so you're only ever working with children of the root node, and you never run into the (somewhat) special case of inserting the root node itself.