ES 2 ( 07.02.2023 )

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 30

// Define structure for list node
typedef struct list_t{
    char *name;
    struct list_t *next;
}list_t;

// Define structure for BST node
typedef struct bst_t{
    int id;
    struct bst_t *left;
    struct bst_t *right;
    struct list_t *head;

}bst_t;

// Function Prototypes
bst_t *insertBST(bst_t *root, int id, char *name);
bst_t *createBSTNode(int id, char *name);
list_t *createListNode(char *name);
void inOrderTraversal(bst_t *root);
bst_t *insert(char *fileName);
void freeBST(bst_t *root);

// Main Function
int main(void){
    bst_t *root = NULL;
    root = insert("../input.txt");
    inOrderTraversal(root);

    freeBST(root);
    return EXIT_SUCCESS;
}

// Function Declarations

bst_t *insert(char *fileName){
    FILE *fp;
    bst_t *root = NULL;
    char name[MAX];
    int id;

    fp = fopen(fileName,"r");
    if(fp == NULL){
        fprintf(stderr,"Error opening file\n");
        exit(EXIT_FAILURE);
    }

    while (fscanf(fp,"%d %s", &id, name) != EOF){
        root = insertBST(root,id,name);
    }

    fclose(fp);
    return root;
}

bst_t *insertBST(bst_t *root, int id, char *name){
    if(root == NULL){
        return createBSTNode(id, name);
    }

    if(id < root->id){
        root->left = insertBST(root->left, id, name);
    }else if(id > root->id){
        root->right = insertBST(root->right, id, name);
    }else{
        // Create node list
        list_t *current = createListNode(name);
        current->next = root->head;
        root->head = current;
    }

    return root;
}


bst_t *createBSTNode(int id, char *name){
    bst_t *newNode = (struct bst_t *) malloc (sizeof (bst_t));
    if(newNode == NULL){
        fprintf(stderr,"Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->id = id;
    newNode->left = NULL;
    newNode->right = NULL;

    newNode->head = createListNode(name);

    return newNode;
}

list_t *createListNode(char *name){
    list_t *newNode = (struct list_t *) malloc (sizeof (list_t));
    if(newNode == NULL){
        fprintf(stderr,"Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }

    newNode->name = strdup(name);
    newNode->next = NULL;

    return newNode;
}


void inOrderTraversal(bst_t *root){
    if(root == NULL){
        return;
    }

    inOrderTraversal(root->left);

    fprintf(stdout,"- %d: ", root->id);
    list_t *current = root->head;
    while (current != NULL){
        fprintf(stdout,"%s ", current->name);
        current = current->next;
    }
    fprintf(stdout,"\n");

    inOrderTraversal(root->right);
}

void freeBST(bst_t *root){
    if(root == NULL){
        return;
    }

    freeBST(root->left);
    freeBST(root->right);

    list_t *current = root->head;
    while (current != NULL){
        list_t *tmp = current;
        current = current->next;
        free(tmp->name);
        free(tmp);
    }

    free(root);
}