Simple Int Binary Tree Implementation For C

tree.c

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

struct Node {
    int key;
    void *data;
    struct Node *left, *right, *parent;
};

struct Node *insertNode(struct Node *node, int key, void *data) {
    struct Node *newnode, **target;

    if (node == NULL) {
        newnode = malloc(sizeof(struct Node));
        *newnode = (struct Node) {key, data, NULL, NULL, NULL};
        return newnode;
    }

    if (node->key == key) {
        node->data = data;
        return node;
    }

    if (key < node->key)
        target = &node->left;
    else if (node->key < key)
        target = &node->right;

    *target = insertNode(*target, key, data);
    (*target)->parent = node;

    return node;
}

void *searchNode(struct Node *node, int key) {
    struct Node *result = NULL;

    if (node == NULL)
        return NULL;

    else if (key == node->key)
        return node;

    else if (key < node->key)
        result = node->left;

    else if (node->key < key )
        result = node->right;

    return searchNode(result, key);

}

int deleteNode(struct Node *node, int key) {
    struct Node *entry = NULL, **origplace = NULL, *target = NULL;
    int caseval = 0;

    entry = searchNode(node, key);

    if (entry == NULL) return 1;

    if (entry->parent->left == entry) origplace = &entry->parent->left;
    else origplace = &entry->parent->right;

    caseval = (entry->left != NULL) + (entry->right != NULL);

    if (caseval == 0) {
        free(node);

    } else if (caseval == 1) {
        if (entry->left != NULL) target = entry->left;
        else target = entry->right;

        *origplace = target;
        target->parent = entry->parent;

        free(entry);

    } else if (caseval == 2) {
        target = entry->right;

        while (target->left != NULL) target = target->left;

        entry->key = target->key;
        entry->data = target->data;

        deleteNode(target, target->key);
    }

    return 0;
}

void *treeSort(struct Node *node) {
    if (node->left != NULL)
        treeSort(node->left);
    
    printf("%d\n", node->key);

    if (node->right != NULL)
        treeSort(node->right);

    return 0;
}

void freeNode(struct Node *node) {
    if (node->left != NULL)
        freeNode(node->left);

    if (node->right != NULL)
        freeNode(node->right);

    free(node);
}

int main(void) {
    struct Node *node = insertNode(NULL, 8, NULL);
    insertNode(node, 5, NULL);
    insertNode(node, 6, NULL);
    insertNode(node, 2, NULL);
    insertNode(node, 3, "lol");
    insertNode(node, 10, NULL);
    insertNode(node, 9, "meow");
    insertNode(node, 7, NULL);
    insertNode(node, 11, NULL);
    treeSort(node);
    printf("%s\n", (char *)searchNode(node, 3));
    printf("%s\n", (char *)searchNode(node, 9));
    freeNode(node);
    return 0;
}