#include <iostream>
#include <string>
#include <vector>
#include <fstream>


struct BstNode
{ //structuring a node
    std::string data;
    BstNode* left;
    BstNode* right;
    int frequ;
};

BstNode* NewNodeCreator(std::string data)  //creating a new node, pointing left and right to null
{
    /*I make a pointer, pointing to a new space in memory. To allocate that memory I am using new operator, taking sizeof(BstNode) struct*/
    BstNode* newNode = new BstNode();

    newNode->data = data;
    newNode->left = newNode->right = NULL; // left and right poiners to NULL
    newNode->frequ = 1; //for first time in BST
    return newNode;
}

std::vector<std::string> readFromTxt()
{ //extracting words for a text file
    std::ifstream book("text.txt"); //open and read txt file
    std::string word;
    std::vector<std::string> list;

    if (!book.is_open())
    {
        std::cout << "Unable to open file";
        system("pause");
        exit(1);
    }
    while (book >> word)
    {
        list.emplace_back(word); //store the words in a vector
    }
    return list;
}

BstNode* InsertNode(BstNode* root, std::string data)
{ //inserting node and creating a binary tree
    if (root == NULL)
    {
        return NewNodeCreator(data);
    }
    if (data == root->data) // If the string already exists in BST, count+1 and return
    {
        (root->frequ)++;
        return root;
    }
    else if (root->data > data)
    {
        root->left = InsertNode(root->left, data);
    }
    else
    {
        root->right = InsertNode(root->right, data);
    }
    return root;
}

void InPreorder(BstNode* root) //function for ptinting the BST in pre-order
{
    if (root == NULL)
        return;
    // print data of node
    std::cout << "<" << root->frequ << ">" << " " << root->data << "n";

    //going to left node
    InPreorder(root->left);

    //going to right
    InPreorder(root->right);
}

void Search(BstNode* root, std::string data) //serching through the BST for specific word
{
    if (root == NULL)
    {
        std::cout << "Not foundn";
        return;
    }

    else if (root->data == data)
    {
        std::cout << "Foundn";
    }
    else if (data < root->data)
    {
        std::cout << "Goind leftn";
        return Search(root->left, data);
    }
    else {
        std::cout << "Goind rightn";
        return Search(root->right, data);
    }
}

BstNode* minValue(BstNode* root) //easy way to find the min value in the leftmost leaf
{
    BstNode* minData = root;

    while (minData->left != NULL)
    {
        minData = minData->left;
    }
    return minData;
}

BstNode* NodeDestructor(BstNode* root, std::string data) //deleting a node in BST
{
    if (root == NULL)
    {
        return root;
    }
    if (data < root->data)  // Searching in BST for the value
    {
        root->left = NodeDestructor(root->left, data);
    }
    else if (data > root->data)
    {
        root->right = NodeDestructor(root->right, data);
    }
    else //when the value is found
    {
        if (root->left == NULL && root->right == NULL) //for node with no child
        {
            delete root;
            root = NULL;
        }
        else if (root->left == NULL)//only one child
        {
            BstNode *temp = root->right;
            delete root;
            return temp;
        }
        else if (root->right == NULL)
        {
            BstNode *temp = root->left;
            delete root;
            return temp;
        }
        else //for node with two children
        {
            BstNode* minData = root->right;

            while (minData->left != NULL)
            {
                minData = minData->left;
            }
            return minData;

            BstNode *temp = minData;
            root->data = temp->data;
            root->right = NodeDestructor(root->right, temp->data);
        }
    }
    return root;
}

bool isBST(BstNode* root, BstNode* left = NULL, BstNode* right = NULL)  //funciton for checking if the tree is properly created
{                                                                    // Base condition
    if (root == NULL)
    {
        return true;
    }

    if (left != NULL and root->data < left->data)
    {
        return false;
    }

    if (right != NULL and root->data > right->data)
    {
        return false;
    }
    // check recursively for every node.
    return isBST(root->left, left, root) and isBST(root->right, root, right);
}

int main()
{
    BstNode* root = NULL;
    int i, note, j;
    std::vector<std::string> test; //define a vector to store words from txt file
    test = readFromTxt();

    for (j = 0; j < test.size(); j++) //This loop is bulding the three passing english words
    {
        std::string str1 = test[j];

        root = InsertNode(root, str1);
    }

    if (isBST(root, NULL, NULL)) //calling BST check function
    {
        std::cout << "Is BSTn";
    }
    else
    {
        std::cout << "Not a BSTn";
    }


    InPreorder(root);
    Search(root, "in");
    NodeDestructor(root, "in");
    InPreorder(root);
    Search(root, "in");

    delete root;
    return 0;
}

BstNode* NewNodeCreator(std::string data)  //creating a new node, pointing left and right to null
{
    /*I make a pointer, pointing to a new space in memory. To allocate that memory I am using new operator, taking sizeof(BstNode) struct*/
    BstNode* newNode = new BstNode();

    newNode->data = data;
    newNode->left = newNode->right = NULL; // left and right poiners to NULL
    newNode->frequ = 1; //for first time in BST
    return newNode;
}

std::vector<std::string>   list;
...
while (book >> word)
{
    list.emplace_back(word); //store the words in a vector
}

// Iterate over a stream and build a vector.
std::vector<std::string>   list(std::istream_iterator<std::string>(book),
                                std::istream_iterator());

if (!book.is_open())
{
    std::cout << "Unable to open file";
    system("pause");
    exit(1);
}

if (!book.is_open()) {
    throw std::runtime_errir("Unable to open file");
}

BstNode* InsertNode(BstNode* root, std::string data);

root = InsertNode(root, "Blob");

class BSTTree
{
    private:
        BSTNode*   root;

        void InsertNode(BSTNode* node, std::string data);
    public:
        BSTTree()
            : root(nullptr)
        {}
        void InsertNode(std::string data) {
            root = InsertNode(root, data);
        }
}

else //for node with two children
    {
        BstNode* minData = root->right;

        while (minData->left != NULL)
        {
            minData = minData->left;
        }
        return minData;             // This return is wrong.

        BstNode *temp = minData;
        root->data = temp->data;
        root->right = NodeDestructor(root->right, temp->data);
    }

else //for node with two children
    {
        BstNode* minData = minValue(root->right);

        root->data  = minData->data;
        root-> frequ= minData-> frequ;
        root->right = NodeDestructor(root->right, root->data);
    }