Hi, stack. I've got a binary tree of type TYPE (TYPE is a typedef of data*) that can add and remove elements. However for some reason certain values added will overwrite previous elements. Here's my code with examples of it inserting without overwriting elements and it not overwriting elements.

the data I'm storing:

struct data {
int number;
char *name;

};

typedef struct data data;

# ifndef TYPE
# define TYPE      data*
# define TYPE_SIZE sizeof(data*)
# endif

The tree struct:

struct Node {
TYPE         val;
struct Node *left;
struct Node *rght;

};

struct BSTree { struct Node *root; int cnt; };

The comparator for the data.

int compare(TYPE left, TYPE right) {
int left_len; int right_len; int shortest_string;

/* find longest string */
left_len = strlen(left->name);
right_len = strlen(right->name);
if(right_len < left_len) { shortest_string = right_len; } else { shortest_string = left_len; }

/* compare strings */
if(strncmp(left->name, right->name, shortest_string) > 1) {
    return 1;
}
else if(strncmp(left->name, right->name, shortest_string) < 1) {
    return -1;
}
else {
    /* strings are equal */

    if(left->number > right->number) {
        return 1;
    }
    else if(left->number < right->number) {
        return -1;
    }
    else {
        return 0;
    }
}

}

And the add method

struct Node* _addNode(struct Node* cur, TYPE val) {
if(cur == NULL) {
    /* no root has been made */
    cur = _createNode(val);

    return cur;
}
else {
    int cmp;

    cmp = compare(cur->val, val);
    if(cmp == -1) {
        /* go left */

        if(cur->left == NULL) {
            printf("adding on left node val %d\n", cur->val->number);
            cur->left = _createNode(val);
        }
        else {
            return _addNode(cur->left, val);
        }
    }
    else if(cmp >= 0) {
        /* go right */

        if(cur->rght == NULL) {
            printf("adding on right node val %d\n", cur->val->number);
            cur->rght = _createNode(val);
        }
        else {
            return _addNode(cur->rght, val);
        }
    }

    return cur;
}

}

void addBSTree(struct BSTree *tree, TYPE val)
{
tree->root = _addNode(tree->root, val);
tree->cnt++;
}

The function to print the tree:

void printTree(struct Node *cur) {
if (cur == 0) {
    printf("\n");
}
else {
    printf("(");
    printTree(cur->left);
    printf(" %s, %d ", cur->val->name, cur->val->number);
    printTree(cur->rght);
    printf(")\n");
}

}

Here's an example of some data that will overwrite previous elements:

struct BSTree myTree;
struct data myData1, myData2, myData3;

myData1.number = 5;
myData1.name = "rooty";
myData2.number = 1;
myData2.name = "lefty";
myData3.number = 10;
myData3.name = "righty";

initBSTree(&myTree);
addBSTree(&myTree, &myData1);
addBSTree(&myTree, &myData2);
addBSTree(&myTree, &myData3);
    printTree(myTree.root);

Which will print:

((
 righty, 10 
)
 lefty, 1 
)

Finally here's some test data that will go in the exact same spot as the previous data, but this time no data is overwritten:

struct BSTree myTree;
struct data myData1, myData2, myData3;

myData1.number = 5;
myData1.name = "i";
myData2.number = 5;
myData2.name = "h";
myData3.number = 5;
myData3.name = "j";

initBSTree(&myTree);
addBSTree(&myTree, &myData1);
addBSTree(&myTree, &myData2);
addBSTree(&myTree, &myData3);
printTree(myTree.root);

Which prints:

((
 j, 5 
)
 i, 5 (
 h, 5 
)
)

Does anyone know what might be going wrong? Sorry if this post was kind of long.