Cant insert Node to binary tree

Question

I am trying to insert Node to Binary tree. This is my function for creating Node (rest is done).

void BVSCreate_function(TNodef *rootPtr, function_save token) {
    TNodef *newPtr = malloc(sizeof(struct tnodef));
    if (newPtr == NULL) {
        fprintf(stderr, "99");
        return;
    }
    TNodef init;
    string initStr;
    initStr.str = NULL;
    initStr.length = 0;
    initStr.alloc = 0;
    newPtr = &init;
    newPtr->content = &initStr;
    newPtr->leftPtr = NULL;
    newPtr->rightPtr = NULL;
    newPtr->return_type = token.ret_value;
    newPtr->parameters = token.param_count;
    strCpyStr(newPtr->content, token.content);
    rootPtr = newPtr;
}

void BVSInsert_function(TNodef *rootPtr, function_save token) {
    if (rootPtr == NULL) {
        BVSCreate_function(rootPtr, token);
    } else {
        if ((strCmpStr(token.content, rootPtr->content)) < 0) {
            BVSCreate_function(rootPtr->leftPtr, token);
        } else
        if ((strCmpStr(token.content, rootPtr->content)) > 0) {
            BVSCreate_function(rootPtr->rightPtr, token);
        }
    }
}

When TNodef and function_save are structs:

typedef struct {
    string *content;
    int param_count;
    int ret_value;
} function_save;

typedef struct tnodef {
    string *content;
    struct tnodef *leftPtr;
    struct tnodef *rightPtr;
    int parameters;
    int return_type;
} TNodef;

Where string is defined as this struct:

typedef struct {
    char *str;  // content of string
    int length; // length of string
    int alloc;  // amount of memory allocated
} string;

strCpystr function :

int strCpyStr(string *s1, string *s2) {
    int len2 = s2->length;
    if (len2 > s1->alloc) {
        if (((s1->str) = (char *)realloc(s1->str, len2 + 1)) == NULL) {
            return 1;
        }
        s1->alloc = len2 + 1;
    }
    strcpy(s1->str, s2->str);
    s1->length = len2 + 1;
    return 0;
}

I am trying to create a node in binary tree and put there information from struct function_save. But when I try to print this tree after insert it shows me that tree is still empty.

Answer 1

Your code in BVSCreate_function has undefined behavior because:

• newPtr = &init; discards the allocated node and instead uses a local structure that will become invalid as soon as the function returns.

• newPtr->content = &initStr; is incorrect for the same reason: you should allocate memory for the string too or possibly modify the TNodeDef to make content a string object instead of a pointer.

Function BVSInsert_function does not return the updated root pointer, hence the caller's root node is never updated. You could change the API, passing the address of the pointer to be updated.

There is also a confusion in BVSInsert_function: it should call itself recursively when walking down the tree instead of calling BVSCreate_function.

Here is a modified version:

/* Allocate the node and return 1 if successful, -1 on failure */
int BVSCreate_function(TNodef **rootPtr, function_save token) {
    TNodef *newPtr = malloc(sizeof(*newPtr));
    string *newStr = malloc(sizeof(*content));
    if (newPtr == NULL || newStr == NULL) {
        fprintf(stderr, "99");
        free(newPtr);
        free(newStr);
        return -1;
    }
    newStr->str = NULL;
    newStr->length = 0;
    newStr->alloc = 0;
    newPtr->content = newStr;
    newPtr->leftPtr = NULL;
    newPtr->rightPtr = NULL;
    newPtr->return_type = token.ret_value;
    newPtr->parameters = token.param_count;
    strCpyStr(newPtr->content, token.content);
    *rootPtr = newPtr;
    return 1;
}

int BVSInsert_function(TNodef **rootPtr, function_save token) {
    if (*rootPtr == NULL) {
        return BVSCreate_function(rootPtr, token);
    } else {
        if (strCmpStr(token.content, rootPtr->content) < 0) {
            return BVSInsert_function(&rootPtr->leftPtr, token);
        } else
        if ((strCmpStr(token.content, rootPtr->content)) > 0) {
            return BVSInsert_function(&rootPtr->rightPtr, token);
        } else {
            /* function is already present: return 0 */
            return 0;
        }
    }
}

Note also that function strCpyStr may write beyond the end of the allocated area is len2 == s1->alloc, assuming s1->len is the length of the string, excluding the null terminator.

Here is a modified version:

int strCpyStr(string *s1, const string *s2) {
    int len2 = s2->length;
    if (len2 >= s1->alloc) {
        char *newstr = (char *)realloc(s1->str, len2 + 1);
        if (newstr == NULL) {
            return 1;
        }
        s1->str = newstr;
        s1->alloc = len2 + 1;
    }
    strcpy(s1->str, s2->str);
    s1->length = len2;
    return 0;
}