Provides a C implementation of a binary tree along with many tree-related functions

binarytree.c

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

struct tree_node
{
    int data;
    struct tree_node *left, *right;
};

struct tree_node *create_node(int data)
{
    struct tree_node *tmp = (struct tree_node*)malloc(sizeof (struct tree_node));
    tmp->data = data;
    tmp->left = NULL;
    tmp->right = NULL;
    return tmp;
}

void delete_tree(struct tree_node *root)
{
    if(root == NULL)
        return;

    struct tree_node *right = root->right;

    delete_tree(root->left);
    free(root);
    delete_tree(right);
}

void in_order_traversal(struct tree_node *root)
{
    if(root == NULL)
        return;

    in_order_traversal(root->left);
    printf("%d ", root->data);
    in_order_traversal(root->right);
}

// in order, pre order, post order, level order

void pre_order_traversal(struct tree_node *root)
{
    if(root == NULL)
        return;

    printf("%d ", root->data);
    pre_order_traversal(root->left);
    pre_order_traversal(root->right);
}

void post_order_traversal(struct tree_node *root)
{
    if(root == NULL)
        return;

    post_order_traversal(root->left);
    post_order_traversal(root->right);
    printf("%d ", root->data);
}

int tree_height(struct tree_node *root)
{
    if(root == NULL)
        return 0;

    int left_height = tree_height(root->left);
    int right_height = tree_height(root->right);

    if(left_height > right_height)
        return 1 + left_height;

    return 1 + right_height;
}

void level_order_helper(struct tree_node *root, int height)
{
    if(root == NULL)
        return;

    if(height == 0)
    {
        printf("%d ", root->data);
    } else if(height > 0) {

        level_order_helper(root->left, height - 1);
        level_order_helper(root->right, height - 1);
    }
}

void level_order_traversal(struct tree_node *root)
{
    int i = 0;
    int height = tree_height(root);

    for(i = 0; i < height; ++i)
        level_order_helper(root, i);

}

int search_anytree(struct tree_node *root, int value)
{
    if(root == NULL)
        return 0;

    if(root->data == value)
        return 1;

    return search_anytree(root->left, value) || search_anytree(root->right, value);
}

int search_binary(struct tree_node *root, int value)
{
    if(root == NULL)
        return 0;

    if(value < root->data)
        return search_binary(root->left, value);
    if(value > root->data)
        return search_binary(root->right, value);
    else
        return 1;
}

int find_max(struct tree_node *root)
{
    if(root->right == NULL)
        return root->data;

    return find_max(root->right);
}

int find_min(struct tree_node *root)
{
    if(root->left == NULL)
        return root->data;

    return find_min(root->left);
}

struct tree_node *find_node(struct tree_node *root, int value)
{
    if(root != NULL)
    {
        if(value < root->data)
            return find_node(root->left, value);
        else if(value > root->data)
            return find_node(root->right, value);
        else
            return root;
    }
}

struct tree_node *parent(struct tree_node *root, int value)
{
    // value must be a valid node in the binary tree
    if(root != NULL)
    {
        if(root->data == value)     // if value is the root of the tree
            return NULL;
        else if(root->left != NULL && root->left->data == value)
            return root;
        else if(root->right != NULL && root->right->data == value)
            return root;
        else if(value < root->data)
            return parent(root->left, value);
        else if(value > root->data)
            return parent(root->right, value);
    }
}

int is_leaf(struct tree_node *node)
{
    return node->left == NULL && node->right == NULL;
}

int only_left_child(struct tree_node *node)
{
    if(node == NULL)
        return 0;

    return node->left != NULL && node->right == NULL;
}

int only_right_child(struct tree_node *node)
{
    if(node == NULL)
        return 0;

    return node->left == NULL && node->right != NULL;
}


struct tree_node *delete_node(struct tree_node *root, int value)
{
    struct tree_node *node = find_node(root, value);

    if(node == NULL)
    {
        printf("Could not find value: %d\n", value);
        return root;
    }

    struct tree_node *ancestor = parent(root, node->data);

    if(is_leaf(node))
    {
        if(ancestor != NULL)
        {
            if(ancestor->left != NULL && ancestor->left->data == node->data)
                ancestor->left = NULL;
            else if(ancestor->right != NULL && ancestor->right->data == node->data)
                ancestor->right = NULL;
        } else {
            root = NULL;
        }
        free(node);

    } else if(only_left_child(node)) {

        if(ancestor != NULL)
        {
            if(ancestor->left != NULL && ancestor->left->data == node->data)
                ancestor->left = node->left;
            else if(ancestor->right != NULL && ancestor->right->data == node->data)
                ancestor->right = node->left;
        } else {
            root = node->left;
        }
        free(node);

    } else if(only_right_child(node)) {

        if(ancestor != NULL)
        {
            if(ancestor->left != NULL && ancestor->left->data == node->data)
                ancestor->left = node->right;
            else if(ancestor->right != NULL && ancestor->right->data == node->data)
                ancestor->right = node->right;
        } else {
            root = node->right;
        }
        free(node);

    } else {    // the node has two children

        struct tree_node *min_right = find_node(root, find_min(node->right));
        struct tree_node *min_parent = parent(root, min_right->data);

        if(node->data == min_parent->data) // edge case if the node to delete only has one right child
        {
            min_right->left = node ->left;
            min_right->right = NULL;
        } else {
            min_parent->left = min_right->right;
            min_right->left = node->left;
            min_right->right = node->right;
        }

        if(ancestor == NULL)
            root = min_right;
        else if(ancestor->left != NULL && ancestor->left->data == node->data)
            ancestor->left = min_right;
        else if(ancestor->right != NULL && ancestor->right->data == node->data)
            ancestor->right = min_right;

        free(node);
    }

    return root;
}

struct tree_node *insert(struct tree_node *root, int value)
{
    if(root == NULL)
        return create_node(value);

    if(value < root->data && (only_right_child(root) || is_leaf(root)))
        root->left = create_node(value);
    else if(value > root->data && (only_left_child(root) || is_leaf(root)))
        root->right = create_node(value);
    else if(value < root->data)
        insert(root->left, value);
    else if(value > root->data)
        insert(root->right, value);

    return root;
}

struct tree_node *array_to_tree(struct tree_node *root, int *values, int len)
{
    // array must be in level-order traversal
    int i = 0;
    for( ; i < len; ++i)
        root = insert(root, values[i]);

    return root;
}

struct tree_node *file_to_tree(const char *input, struct tree_node *root)
{
    FILE *input_file = fopen(input, "r");
    if(!input_file)
    {
        printf("Unable to open file: %s", input);
        return NULL;
    }

    if(root)
        root = delete_tree(root);

    while(!feof(input_file))
    {
        int data;
        fscanf(input_file, "%d", &data);
        root = insert(root, data);
    }

    fclose(input_file);

    return root;
}

int main()
{
/*
            30
          /    \
        15      45
       /  \    /  \
      5    23 39   50
          /  /
        18  36
*/

#define GUINIE_PIG 18
#define DELETE_VALUE 30
#define INSERT_VALUE 6

    // array must be in level-order traversal
    int values[] = {30, 15, 45, 5, 23, 39, 50, 18, 36};

    struct tree_node *root = NULL;
    root = array_to_tree(root, values, sizeof values / sizeof values[0]);

    printf("In-order traversal: ");
    in_order_traversal(root);
    putchar('\n');

    printf("Pre-order traversal: ");
    pre_order_traversal(root);
    putchar('\n');

    printf("Post-order traversal: ");
    post_order_traversal(root);
    putchar('\n');

    printf("Tree height: %d", tree_height(root));
    putchar('\n');

    printf("Level-order traversal: ");
    level_order_traversal(root);
    putchar('\n');

    printf("Result of search for %d: %s\n",
           GUINIE_PIG,
           search_binary(root, GUINIE_PIG) ? "Found" : "Not Found");

    printf("Minimum: %d\n", find_min(root));
    printf("Maximum: %d\n", find_max(root));

    printf("Get node with value %d\nGot %#p\n",
           GUINIE_PIG,
           find_node(root, GUINIE_PIG));

    printf("Get parent of %d: %d\n",
           GUINIE_PIG,
           parent(root, GUINIE_PIG)->data);

    printf("Attempting to delete: %d\n", DELETE_VALUE);
    root = delete_node(root, DELETE_VALUE);
    printf("In-order after deletion:\n");
    in_order_traversal(root);
    putchar('\n');

    printf("Inserting the value %d\n", INSERT_VALUE);
    root = insert(root, INSERT_VALUE);
    printf("In-order after insertion:\n");
    in_order_traversal(root);
    putchar('\n');

    delete_tree(root);

    return 0;
}