/*
 *
 * THIS IS A TEST FILE FOR BINARY_TREE.C 
 *
 * Binary Tree Coded by Anastasios Ksouzafeiris (c) 2010
 * For contact anastasis.ksouzafeiris[at]gmail[dot]com
 *
 */
 
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
 
#define EXIT 0
#define ADD  1 
#define FIND 2
#define DEL  3
#define SHOW 4

struct node
{
        int data;
        struct node *left;
        struct node *right;
};
 
struct node *root;
struct node *newnode();
struct node *find();
struct node *insert();
struct node *find_left_most();
struct node *find_right_most();
void display();
 
int main()
{
    int ch;
    int a;
    struct node *new;
    root = NULL;

    while(1)
        {
            printf("|0 -> Eksodos | 1 -> Add | 2 -> Find ");
            printf("|3 -> Delete  | 4 -> Show :\n");
            //ch = getchar();
            scanf("%d", &ch);
            switch(ch)
                {
                case EXIT:
                    return 0;
                case ADD:
                    printf("num:");
                    scanf("%d",&a);
                    new = insert(a);
                    if (root == NULL)
                        root = new;
                    if(new == NULL)
                        puts("Not enough memory");
                    break;
                case FIND:
                    printf("num:");
                    scanf("%d",&a);
                    new = find(a);
                    if(new != NULL)
                        printf("Found!\n");
                    else
                        printf("There is no match!\n");
                    break;
                case DEL:
                    printf("num:");
                    scanf("%d",&a);
                    rm(a);
                    break;
                default:
                    puts("Wrong press!");
                    break;
                }
        }
}

struct node *newnode(int num)
{
        struct node *neos;
        neos = malloc(sizeof(struct node));
        neos->data = num;
        neos->left = NULL;
        neos->right = NULL;
        return(neos);
}
 
void display(struct node *ptr)
{
        if (ptr == NULL) 
                return;
        display(ptr->left);
        printf("%d", ptr->data);
        display(ptr->right);
}
 
struct node *find(int key)
{
        struct node *current;
        current = root;
        while(current->data != key)
        {
                if(key < current->data)
                        current = current->left;
                else
                        current = current->right;
                if(current == NULL)
                        return NULL;
        }
        return current;
}
 
struct node *insert(int num)
{
        struct node *next,*current,*ptr;
        int isleft;
        next = current = root;
        ptr=newnode(num);
        if (root == NULL)
        {
                return ptr;
        }
        while(1)
        {
                if(num < current->data)
                {
                        next = current->left;
                        isleft = 1;
                }
                else
                {
                        next = current->right;
                        isleft = 0;
                }
                if(next == NULL)
                {
                        if(isleft)
                                current->left = ptr;
                        else
                                current->right = ptr;
                        return ptr;
                }
                current = next;
        }
}
 
// Delete node with key "key"
int rm(int key)
{
        struct node *current;
        struct node *parent;
        int isLeftChild = 1;
        current = parent = root;
        while(current->data != key)
        {
                parent = current;
                if(key < current->data)
                {
                        isLeftChild = 1;
                        current = current->left;
                }
                else
                {
                        isLeftChild = 0;
                        current = current->right;
                }
                if(current == NULL)
                        return 0;
        }
        // Node with key "key" found. His address is at pointer "current"
        // and his parent's address is at pointer "parent"
 
        // if the node does not have affiliates
        if(current->left == NULL && current->right == NULL)
        {
                if(current == root)     // if it is root
                        root = NULL;    // the tree is blank
                else if(isLeftChild)
                        parent->left = NULL;    // disconnection
                else                            // from parent
                        parent->right = NULL;
        }
 
        // if does not have left filial node
        else if(current->right == NULL)
        {
                if(current == root)
                        root = current->left;
                else if(isLeftChild)
                        parent->left = current->left;
                else
                        parent->right = current->left;
        }
 
        // if does not have right filial node
        else if(current->left == NULL)
        {
                if(current == root)
                        root = current->right;
                else if(isLeftChild)
                        parent->left = current->right;
                else
                        parent->right = current->right;
        }
 
        // if there is left & right filial node
        else
        {
                struct node *successor,*temp,*old_root;
                if(current == root)
                {
                        temp = root->left;
                        successor = find_left_most(root->right);
                        root = root->right;
                        successor->left = temp;
                }
                else if(isLeftChild)
                {
                        successor = find_left_most(current->right);
                        successor->left = current->left;
                        parent->left = current->right;
                }
                else
                {
                        successor = find_right_most(current->left);
                        successor->right = current->right;
                        parent->right = current->left;
                }
        }
        free(current); //releases memory allocation of the node
        return 1;
}
 
// identify/detect the leftmost node of the subtree rt
struct node *find_left_most(struct node *rt)
{
        if(rt == NULL)
                return NULL;
        while(rt->left != NULL)
        {
                rt = rt->left;
        }
        return rt;
}
 
// identify/detect the rightmost node of the subtree rt
struct node *find_right_most(struct node *rt)
{
        if(rt == NULL)
                return NULL;
        while(rt->right != NULL)
        {
                rt = rt->right;
        }
        return rt;
}