C Binary Search Tree Implementation. Adding, searching, ordering, and tree deletion included.

bst.c

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

// Node Structure
typedef struct node {
    // Ordered from grestest member size to smallest member size for reducing memory used.
    struct node *left; // Pointer pointing to left child node.
    struct node *right; // Pointer pointing to right child node.
    int val; // The value the node is holding.
} node_t;

// Prototypes
void printInOrder(node_t *parent);
bool contains(node_t *parent, const int *value);
bool addValueToTree(node_t *root, const int *value);
void delete(node_t *parent);

int main() {
    node_t* root = NULL;
    root = malloc(sizeof(node_t));

    if (root == NULL) {
        printf("Could not allocate memory for root node.\n");
        return -1;
    }

    // Seed random so we always get the same values.
    srand(1337);

    // Fill Tree with values.
    root->left = NULL;
    root->right = NULL;
    root->val = rand();

    int i = 0;
    for (; i < 4; i++) {
        int randomNumber = rand();
        printf("Adding %d\n", randomNumber);
        bool success = addValueToTree(root, &randomNumber);
    }

    // Test out Sorting and Searching.
    printInOrder(root);
    int toFind = 29;
    bool found = contains(root, &toFind);
    printf("\nDoes this tree contain %d? %s\n", toFind, (found == false) ? "No" : "Yes");
    toFind = 524664131;
    found = contains(root, &toFind);
    printf("Does this tree contain %d? %s\n", toFind, (found == false) ? "No" : "Yes");
    delete(root);

    return 0;
}

void printInOrder(node_t *parent) {
    // Safety Check.
    if (parent == NULL) {
        return;
    }

    // Print Left Subtree.
    printInOrder(parent->left);

    // Print Parent.
    printf("%d, ", parent->val);

    // Print Right Subtree.
    printInOrder(parent->right);
}

bool contains(node_t *parent, const int *value) {
    // Safety Check.
    if (parent == NULL) {
        return false;
    }

    // Found match!
    if (parent->val == *value) {
        return true;
    }

    // Check left subtree.
    if (*value < parent->val) {
        return contains(parent->left, value);
    }

    // Check right subtree.
    return contains(parent->right, value);
}

// Deletes all nodes so we don't have any memory leaks.
void delete(node_t *parent) {
    if (parent == NULL) {
        return;
    }
    
    delete(parent->left);
    delete(parent->right);

    free(parent);
}

// Adds a value to the tree.
bool addValueToTree(node_t *root, const int *value) {
    // Invalid Tree
    if (root == NULL) {
        return false;
    }

    node_t *previous = root;
    node_t *current = root;

    int currentValue = current->val;

    // Find where we should insert this value.
    while (current != NULL) {
        currentValue = current->val;

        // No duplicates allowed.
        if (*value == currentValue) {
            return false;
        }

        previous = current;

        if (*value < currentValue) {
            current = current->left;
        } else {
            current = current->right;
        }
    }

    node_t *created = NULL;

    // Left or Right?
    if (*value < currentValue) {
        previous->left = malloc(sizeof(node_t));
        created = previous->left;
    } else{
        previous->right = malloc(sizeof(node_t));
        created = previous->right;
    }

    // Safety Check.
    if (created == NULL) {
        printf("Could not allocate memory to create a new node.\n");
        return false;
    }

    // Set Values.
    created->val = *value;
    created->left = NULL;
    created-> right = NULL;

    return true;
}