adding nodes to a binary search tree randomly deletes nodes

Question

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 method to create a new node:

struct Node* _createNode(TYPE val) {
struct Node* new_node;
new_node = (struct Node*)malloc(sizeof(struct Node*));
new_node->val = val;
new_node->left = NULL;
new_node->rght = NULL;

return new_node;
}

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.

Answer 1

I don't see an obvious flaw. I would suggest reworking the tree to hold int's or something simpler than your current data. If the tree works fine then at least you know where to look and not worry about the generic tree code.

I suspect _createNode(), can you add that code?

Answer 2

it looks like there is an error in your _addNode procedure. It looks like you arent properly storing the new node references in the tree.

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 */
        cur->left = _addNode(cur->left, val);
    }
    else if(cmp >= 0) {
        /* go right */
        cur->left = _addNode(cur->right, val);
    }

    return cur;
}

the _addnode function was kind of confusing because you were using the return value inconsistently. i believe this version should avoid loosing any nodes.