tree.c

#include "../inc/tree.h"

/**
 * Please correct the contents of this file to make sure all functions here do what they are supposed to do if you find
 * that they do not work as expected.
 */

// Tree function: you are allowed to change the contents, but not the method signature
Tree* tree_create(){
    Tree *tree = malloc(sizeof(Tree));
    tree->root = NULL;

    return tree;
}

// Helper function: you are allowed to change this to your preferences
void tree_node_delete(Node* node) {
    if (node == NULL) return;

    tree_node_delete(node->left);
    tree_node_delete(node->right);

    free(node);
}

// Tree function: you are allowed to change the contents, but not the method signature
void tree_delete(Tree* tree) {
    tree_node_delete(tree->root);

    free(tree);
}

// Helper function: you are allowed to change this to your preferences

void node_insert(Node* node, int age, char* name) {
    if (node == NULL) return; // Sanity check, though this should not occur in normal usage

    if (age <= node->age) {
    	// Case : if left child is null
        if (node->left == NULL) {
            Node* newLeft = malloc(sizeof(Node));  // Allocate memory for the new node
            if (newLeft == NULL) {
                perror("Failed to allocate memory for new node");
                exit(EXIT_FAILURE);
            }

            // Initialize the new node
            newLeft->age = age;
            newLeft->name = strdup(name); // Create a copy of the name string so that node owns its own copy of name
            if (newLeft->name == NULL) {
                perror("Failed to allocate memory for node name");
                free(newLeft); // Clean up partially allocated node
                exit(EXIT_FAILURE);
            }
            newLeft->left = NULL;
            newLeft->right = NULL;

            // Assign the new node as the left child
            node->left = newLeft;
        } else {
            //Case : If left child is not null
	    //Recur into the left subtree
            node_insert(node->left, age, name);
        }
    } else {
    	//Case : if right child is null
        if (node->right == NULL) {
            // Allocate memory for the new node
            Node* newRight = malloc(sizeof(Node));
            if (newRight == NULL) {
                perror("Failed to allocate memory for new node");
                exit(EXIT_FAILURE);
            }

            // Initialize the new node
            newRight->age = age;
            newRight->name = strdup(name); // Create a copy of the name string
            if (newRight->name == NULL) {
                perror("Failed to allocate memory for node name");
                free(newRight); // Clean up partially allocated node
                exit(EXIT_FAILURE);
            }
            newRight->left = NULL;
            newRight->right = NULL;

            // Assign the new node as the right child
            node->right = newRight;
        } else {
	    // if right child is not null
            // Recur into the right subtree
            node_insert(node->right, age, name);
        }
    }
}


// Tree function: you are allowed to change the contents, but not the method signature
void tree_insert(Tree* tree, int age, char* name) {
    if (tree->root == NULL) {
        Node *node = malloc(sizeof(Node));
        if (node == NULL) {
                perror("Failed to allocate memory for new node");
                exit(EXIT_FAILURE);
            }
        node->name = name;
        node->left = NULL;
        node->right = NULL;
        node->age = age;
        tree->root = node;
    } else {
        node_insert(tree->root, age, name);
    }
}

// Helper function: you are allowed to change this to your preferences
void tree_print_node(Node* node){
    if (node == NULL) {
        printf("null");
        return;
    }
    printf("[");
    printf("{\"%d\":\"%s\"},", node->age, node->name);
    tree_print_node(node->left);
    printf(",");
    tree_print_node(node->right);
    printf("]");
}

// Tree function: you are allowed to change the contents, but not the method signature
void tree_print(Tree* tree, int printNewline){
    if (tree == NULL) {
        printf("null");
        return;
    }
    tree_print_node(tree->root);

    if (printNewline){
        printf("\n");
    }
}

// Helper function: you are allowed to change this to your preferences
/*Node* node_find(Node* node, int age, char* name) {
    if(node == NULL){
        return node;
    }
    if (node->age == age && !strcmp(node->name, name)) {
        return node;
    }

    if (age <= node->age) {
        return node_find(node->left, age, name);
    } else {
        return node_find(node->right, age, name);
    }
}

// Tree function: you are allowed to change the contents, but not the method signature
Node* tree_find(Tree* tree, int age, char* name) {
    return node_find(tree->root, age, name);
} */

Node* node_find(Node* node, int age, const char* name) {
    // Base case: if node is NULL, return NULL
    if (node == NULL) {
        return NULL;
    }

    // If the node matches the age and name, return the node
    if (node->age == age && strcmp(node->name, name) == 0) {
        return node;
    }

    // Otherwise, traverse the left or right subtree based on age
    if (age < node->age) {
        return node_find(node->left, age, name);
    } else {
        return node_find(node->right, age, name);
    }
}

// Tree function: calls node_find on the root node
Node* tree_find(Tree* tree, int age, char* name) {
    return node_find(tree->root, age, name);
}


struct Node* minValueNode(struct Node* node) {
    struct Node* current = node;
    // Loop down to find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;
    return current;
}

Node* delete_node(Node* root,int age, char* name, Tree* tree) {
    if (root == NULL)
        return root;

    if (age < root->age)
        root->left = delete_node(root->left, age, name, tree);
    
    else if (age > root->age)
        root->right = delete_node(root->right, age, name, tree);

    else {

        if (root == tree->root) {
            tree->root = root->left ? root->left : root->right;
            return tree->root; // Ensure the updated root is returned
        }

        // Case 1: Node has no children (leaf node)
        if (root->left == NULL && root->right == NULL) {
            free(root);
            root = NULL;
        }
        // Case 2: Node has one child
        else if (root->left == NULL) {
            struct Node* temp = root;
            root = root->right;
            free(temp);
        }
        else if (root->right == NULL) {
            struct Node* temp = root;
            root = root->left;
            free(temp);
        }

        // Case 3: Node has two children
        else {
            // Get the inorder successor (smallest in the right subtree)
            struct Node* temp = minValueNode(root->right);
            // Copy the inorder successor's data to this node
            root->age = temp->age;
            root->name = temp->name;
            // Delete the inorder successor
            root->right = delete_node(root->right, temp->age, temp->name, tree);
        }
    }

    return root;

}


// Tree function: you are allowed to change the contents, but not the method signature
void tree_erase(Tree* tree, int age, char* name) {
    Node* data = tree_find(tree, age, name);
    tree->root = delete_node(tree->root, age, name, tree);
}