typedef struct
{
    char[50] data;
    struct node* left;
    struct node* right;
    struct node* parent;
}node;

node* create_node(int data)
{
    node *new_node = (node*)malloc(sizeof(node));
    if(new_node == NULL)
    {
        fprintf (stderr, "OUT OF MEMORY!!! (create_node)\n");
        exit(1);
    }
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->parent = NULL;
    return new_node;
}

int compare(char *left,char *right)
{
    if(strcmp(left,right)>0)
        return 1;
    else if(strcmp(left,right)<0)
        return -1;
    return 0;
}

node* insert_node(node *root, int data)
{

    if(root == NULL)
    {
        root = create_node(data);
    }
    else
    {
        int is_left  = 0;
        int r        = 0;
        node* cursor = root;
        node* prev   = NULL;

        while(cursor != NULL)
        {
            r = compare(data,cursor->data);
            prev = cursor;
            if(r < 0)
            {
                is_left = 1;
                cursor = cursor->left;
            }
            else if(r > 0)
            {
                is_left = 0;
                cursor = cursor->right;
            }

        }
        if(is_left)
            prev->left = create_node(data);
        else
            prev->right = create_node(data);
    }
    return root;
}

node* delete_node(node* root, int data)
{
    if(root == NULL)
        return NULL;

    node *cursor;
    int r = compare(data,root->data);
    if( r < 0)
        root->left = delete_node(root->left,data);
    else if( r > 0 )
        root->right = delete_node(root->right,data);
    else
    {
        if (root->left == NULL)
        {
            cursor = root->right;
            free(root);
            root = cursor;
        }
        else if (root->right == NULL)
        {
            cursor = root->left;
            free(root);
            root = cursor;
        }
        else    //2 children
        {
            cursor = root->right;
            node *parent = NULL;

            while(cursor->left != NULL)
            {
                parent = cursor;
                cursor = cursor->left;
            }
            root->data = cursor->data;
            if (parent != NULL)
                parent->left = delete_node(parent->left, parent->left->data,compare);
            else
                root->right = delete_node(root->right, root->right->data,compare);
        }
    }
    return root;
}

node* inOrderSuccessor(node *root, node *n)
{
    if( n->right != NULL )
        return minValue(n->right);
    node *succ = NULL;
    while (root != NULL)
    {
        if (n->data < root->data)
        {
            succ = root;
            root = root->left;
        }
        else if (n->data > root->data)
            root = root->right;
        else
           break;
    }
    return succ;
}

node* search(node *root,char *data,comparer compare)
{
    if(root == NULL)
        return NULL;

    int r;
    node* cursor = root;
    while(cursor != NULL)
    {
        r = compare(data,cursor->data);
        if(r < 0)
            cursor = cursor->left;
        else if(r > 0)
            cursor = cursor->right;
        else
            return cursor;
    }
    return cursor;

}

void display_tree(node* nd)
{
    if (nd == NULL)
        return;
    printf("%d",nd->data);
    if(nd->left != NULL)
        printf("(Left kid:%s)",nd->left->data);
    if(nd->right != NULL)
        printf("(Right kid:%s)",nd->right->data);
    printf("\n");

    display_tree(nd->left);
    display_tree(nd->right);
}

void Spellcheck(char* Sentence)
{

}

int main()
{
    FILE *f;
    int i;
    char path[100];
    char[20] Entry[3000];
    char[100] Sentence;
    printf("ENTER FILE PATH (INCLUDING FILENAME AND EXTENSION) \n");
    fgets(path,sizeof(path),stdin);
    path[strlen(path) - 1] = 0;
    f=fopen(path,"r");
    if(f==NULL)
	{
		printf("\n%s\" File NOT FOUND! PRESS ANY KEY TO CONTINUE ...",path);
		getch();
		exit(1);
	}
	else
    {

        while (!feof(f))
        {
            for(i=0;i<3000;i++)
            {
                    fscanf(f,"%s",&Entry[i]);
                    fscanf(f,"\n");
            }
        }
    printf("DICTIONARY LOADED ...\n");
    fclose(f);
    printf("Please enter the sentence to be checked:\n");
    fgets(Sentence,sizeof(Sentence),stdin);
    Sentence[strlen(Sentence) - 1] = 0;
    Spellcheck(Sentence);
    getchar();
    return 0;
}