How to create a binary search tree from string?

Question

I tried to create a Morse encoder-decoder, and I have to do it with binary search tree (not with arrays). The following part supposedly takes a character array (which we created previously from a text file), and creates a search tree based on it.

In the btree_base character array we have the data, in the format: "(letter) (morse code)|(letter) (morse code)|" etc. (eg. e .|t -|z --..| ...).

Note: the string contains the data in such a way that by reading it from beginning to end, a balanced search tree would be created

The creation of the binary tree is unsuccesful, which I know, because when I run the code, the btree_print function does not print anything on the console, and I found that's because a NULL pointer is passed to it.

My question is why is that and how to possibly solve the problem? Did I mess up with the pointers, or I need to use double indirection when I pass the root pointer? I don't really understand ** pointers, so I tried to avoid them.

typedef struct BinTree{
    char letter;
    char code[6];
    struct BinTree *left, *right;
} BTree;

BTree* add(BTree* root, char ch, char* code, int length){
    int i;
    char a;
    if (root == NULL) {
        BTree *new = (BTree*) malloc(sizeof(BTree));
        new->left = new->right = NULL;
        new->letter = ch;
        for(i=0; i<length; i++) new->code[i] = code[i];
        new->code[length] = '\0';
        return new;
    }

    a=root->letter;

    if (ch < a) root->left = add(root->left, ch, code, length);
    else if (ch > a) root->right = add(root->right, ch, code, length);

    return root;
}

void build(BTree* root, char* c, int length){
    int i, size=-1;
    char b, k[6];
    for(i=0; i<length; i++){
        if(size==-1) b=c[i];
        if(c[i]==' ') size=0;
        if(size!=-1 && c[i]!='|'){
            k[size]=c[i];
            size++;
        }
        if(c[i]=='|'){
            k[size]='\0';
            root=add(root, b, k, size);
            size=-1;
        }
    }
}

void btree_print(BTree* root){
    if(root == NULL) return;

    printf("%c %s\n",root->letter,root->code);
    btree_print(root->left);
    btree_print(root->right);
}

void btree_del(BTree* root){
    if(root==NULL) return;

    btree_del(root->left);
    btree_del(root->right);
    free(gyoker);
}

int main(){
    char btree_base[238];
    BTree* bin_root = NULL;

    build(bin_root, btree_base, 238);

    btree_print(bin_root);

    btree_del(bin_root);
    return 0;
}

Answer 1

Because you're passing the root node to build by value, any changes made to it's value won't be reflected to the calling function. So as you've guessed you need to pass in a pointer to the root which would make it a BTree **.

build(&bin_root, btree_base, 238);

Then inside build when you want to access the root node you have to dereference root first by prefixing it with a * like this:

*root=add(*root, b, k, size);

add could also benefit from working like that, rather than returning the updated nodes. Which since build already has a BTree ** means you'd just pass in root as is like this

add(root, b, k, size);