上の表題にもある通り、二分探索木を利用して動的なハッシュマップを自分で作ろうとしたのですが、私が書いた以下のコードは実行しても入力に対して期待された出力をしません。
どのように以下のコードに改善すれば、期待された出力を得られるのでしょうか？
とても読みづらいコードになってしまっていて申し訳ないのですが、アドバイスを頂けると大変助かります。

実行したコード:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef struct tnode{//二分木内のノード
    char* key;
    char* value;
    struct tnode* left;
    struct tnode* right;
} tnode;

tnode* btree_empty()
{
    tnode* t;
    t = (tnode*)malloc(sizeof(tnode));
    t->key = (char*)malloc(sizeof(char)*100);
    t->value = (char*)malloc(sizeof(char)*100);
    t->left = NULL;
    t->right = NULL;
    return t;
}

tnode* btree_insert_helper(tnode* parent, char* key, char* val, tnode* t)
{
    if(t==NULL){
        tnode* node = btree_empty();
        strcpy(node->key, key);
        strcpy(node->value, val);
        if(parent==NULL){
            ;
        }else if(strcmp(parent->key, node->key) < 0){
            parent->right = node;
        }else{
            parent->left = node;
        }
        return node;
    }
    int cmp = strcmp(key, t->key);
    if(cmp<0){
        if(t->left == NULL){
            t->left = btree_empty();
            tnode* node = t->left;
            strcpy(node->key, key);
            strcpy(node->value, val);
            return node;
        }else{
            tnode* node = btree_insert_helper(t, key, val, t->left);
            return node;
        }
    }else if(cmp>0){
        if(t->right == NULL){
            t->right = btree_empty();
            tnode* node = t->right;
            strcpy(node->key, key);
            strcpy(node->value, val);
            return node;
        }else{
            tnode* node = btree_insert_helper(t, key, val, t->right);
            return node;
        }
    }else{
        strcpy(t->value, val);
        return t;
    }
}

tnode* btree_insert(char* key, char* val, tnode* t)
{
    return btree_insert_helper(NULL, key, val, t);
}

tnode** deletemin(tnode* node){
    tnode** res = (tnode**)malloc(2*sizeof(tnode*));
    if(node->left != NULL){
        tnode** temp = deletemin(node->left);
        tnode* min;
        node->left = temp[0];
        min = temp[1];
        res[0] = node;
        res[1] = min;
    }else{
        res[0] = node->right;
        res[1] = node;
    }
    return res;
}

tnode* btree_delete(char* key, tnode* t)
{
    if(t == NULL){
        return NULL;
    }
    int cmp = strcmp(key, t->key);
    if(cmp<0){
        t->left = btree_delete(key, t->left);
        return t;
    }else if(cmp>0){
        t->right = btree_delete(key, t->right);
        return t;
    }else{
        if(t->left == NULL && t->right == NULL){
            return NULL;
        }else if(t->left != NULL && t->right == NULL){
            return t->left;
        }else if(t->left == NULL && t->right != NULL){
            return t->right;
        }else{
            tnode** temp = deletemin(t->right);
            tnode* right = temp[0];
            tnode* min = temp[1];
            free(temp);
            min->right = right;
            min->left = t->left;
            return min;
        }
    }
}

tnode* btree_search(char* key, tnode* t){
    int cmp = 0;
    tnode* result = NULL;

    if(t == NULL){
        result = NULL;
    }else{
        cmp = strcmp(key, t->key);
        if(cmp == 0){
            result = t;
        }else if(cmp < 0){
            result = btree_search(key, t->left);
        }else{
            result = btree_search(key, t->right);
        }
    }

    return result;
}

void btree_destroy(tnode* t)
{
    if(t == NULL){
        ;
    }else{
        btree_destroy(t->left);
        btree_destroy(t->right);
        free(t->key);
        free(t->value);
        free(t);
    }
    return;
}

int main(){
    char command[100];
    char word[100];
    char tango[100];
    tnode *tree = NULL;
    tnode *temp = NULL;

    while(1){
        scanf("%s", command);
        if(strcmp(command, "insert") == 0){
            scanf("%s %s", word, tango);
            temp = btree_insert(word, tango, tree);
            if(tree == NULL){
                tree = temp;
            }
        }else if(strcmp(command, "delete") == 0){
            scanf("%s", word);
            temp = tree_delete(word, tree);
            /*
             if(temp == tree->left){
             tree = tree->left;
             }else if(temp == tree->right){
             tree = tree->right;
             }else{
             ;
             }
             */
        }else if(strcmp(command, "search") == 0){
            scanf("%s", word);
            temp = btree_search(word, tree);
            if(temp == NULL){
                printf("(not found)\n");
            }else{
                printf("%s\n", temp->value);
            }
        }else if(strcmp(command, "quit") == 0){
            break;
        }else{
            printf("ERROR\n");
        }
    }
    btree_destroy(tree);
    return 0;
}

入力の例

insert orange オレンジ
insert apple リンゴ
insert grape 葡萄
insert pear 梨
insert strawberry 苺
insert raspberry 木苺
insert fig 無花果
insert kaki 柿
insert apricot 杏
insert peach 桃
search apricot
insert orange 蜜柑
search orange
delete orange
search orange
search kaki
quit

上の入力に対して期待される出力

杏
蜜柑
(not found)
柿

実際の出力

杏
蜜柑
蜜柑
柿