BinaryTree.h

//
//  BinaryTree.h
//  Data Structures
//
//  Created by Salvador Guerrero on 3/16/16.
//  Copyright © 2016 ByteApps. All rights reserved.
//

/*
 * Binary Tree
 *
 * A samples can be found at: https://github.com/ObjSal/Data-Structures
 */

#ifndef BinaryTree_h
#define BinaryTree_h

#ifndef item_type
#define item_type int
#endif

struct Tree
{
    item_type item;
    struct Tree *parent;
    struct Tree *left;
    struct Tree *right;
};

struct Tree* tree_find_minimum(struct Tree* tree_root)
{
    if (tree_root == NULL) return NULL;

    struct Tree *min;

    for (min = tree_root; min->left != NULL; min = min->left);

    return min;
}

struct Tree* tree_find_maximum(struct Tree* tree_root)
{
    if (tree_root == NULL) return NULL;

    struct Tree *max;

    for (max = tree_root; max->right != NULL; max = max->right);
    
    return max;
}

/*
 * right now it does in-order traversal,
 *
 * if we process the node first then it gives a pre-order traversal.
 * if we process the node last it gives a post-order traversal
 */

void tree_traverse(struct Tree *tree_root)
{
    if (tree_root)
    {
        // traverse left tree
        tree_traverse(tree_root->left);

        // process node, right now it just prints the item value
        printf("%d, \n", tree_root->item);

        // traverse right tree
        tree_traverse(tree_root->right);
    }
}

/*
 * do a post-order traversal to free the whole tree
*/

void tree_free(struct Tree *tree_root)
{
    if (tree_root)
    {
        // traverse left tree
        tree_free(tree_root->left);

        // traverse right tree
        tree_free(tree_root->right);

        // free
        free(tree_root);
    }
}

// don't call this method directly, use "void tree_insert(struct Tree **tree_root, item_type item)" instead.

void _tree_insert(struct Tree **tree_root, item_type item, struct Tree *parent)
{
    if (*tree_root == NULL)
    {
        struct Tree *temp_node = (struct Tree *)calloc(1, sizeof(struct Tree));
        temp_node->item = item;
        temp_node->parent = parent;
        *tree_root = temp_node;     // link into paren't record.

        return;
    }

    if (item < (*tree_root)->item)
    {
        _tree_insert(&((*tree_root)->left), item, *tree_root);
    }
    else
    {
        _tree_insert(&((*tree_root)->right), item, *tree_root);
    }
}

void tree_insert(struct Tree **tree_root, item_type item)
{
    _tree_insert(tree_root, item, NULL);
}

struct Tree* tree_search(struct Tree* tree_root, item_type item)
{
    if (tree_root == NULL) return NULL;

    if (tree_root->item == item) return tree_root;

    if (item < tree_root->item)
    {
        return tree_search(tree_root->left, item);
    }
    else
    {
        return tree_search(tree_root->right, item);
    }
}

void tree_delete(struct Tree **tree_root, item_type item)
{
    struct Tree* node_to_delete = tree_search(*tree_root, item);

    if (!node_to_delete) return;

    // Case 1: leaf node with no children

    if (!node_to_delete->left && !node_to_delete->right)
    {
        // just delete and clear the parent pointer.

        if (node_to_delete->parent)
        {
            if (node_to_delete->parent->left == node_to_delete)
            {
                node_to_delete->parent->left = NULL;
            }
            else
            {
                node_to_delete->parent->right = NULL;
            }
        }
    }

    // Case 2: node with only one child

    if ((!node_to_delete->left && node_to_delete->right) || (node_to_delete->left && !node_to_delete->right))
    {
        struct Tree* child_node = node_to_delete->left != NULL ? node_to_delete->left : node_to_delete->right;

        if (node_to_delete->parent)
        {
            if (node_to_delete->parent->left == node_to_delete)
            {
                node_to_delete->parent->left = child_node;
            }
            else
            {
                node_to_delete->parent->right = child_node;
            }
        }
        else
        {
            *tree_root = child_node;
        }
    }

    // Case 3: node with two children

    if (node_to_delete->left && node_to_delete->right)
    {
        // get the node with of its immediate successor in sorted order.

        struct Tree* successor_node = tree_find_minimum(node_to_delete->right);

        if (successor_node->parent->left == successor_node)
        {
            successor_node->parent->left = NULL;
        }
        else
        {
            successor_node->parent->right = NULL;
        }

        if (node_to_delete->parent)
        {
            if (node_to_delete->parent->left == node_to_delete)
            {
                node_to_delete->parent->left = successor_node;
            }
            else
            {
                node_to_delete->parent->right = successor_node;
            }
        }
        else
        {
            *tree_root = successor_node;
        }

        successor_node->left = node_to_delete->left;
        successor_node->right = node_to_delete->right;
    }

    free(node_to_delete);
}

#endif /* BinaryTree_h */