#include<iostream>
#include<vector>
#include<fstream>
#include<sstream>

#include<string>
#include<algorithm>
using namespace std;
int n = 1;
struct tree

{
    int data;
    struct tree *leftchild;
    struct tree *rightchild;
}*root;

class BST

{

public:
    BST()
    {
        root = NULL;
    }
    void insert(tree * t, tree * newnode)
    {
        if (root == NULL)
        {
            root = new tree;
            root->data = newnode->data;
            root->leftchild = NULL;
            root->rightchild = NULL;
            cout << "Root Node is Added" << endl;
            return;
        }
        if (t->data == newnode->data)
        {
            cout << "Element already in the tree" << endl;
            return;
        }
        if (t->data > newnode->data)
        {
            if (t->leftchild != NULL)
            {
                insert(t->leftchild, newnode);
            }
            else
            {
                t->leftchild = newnode;
                (t->leftchild)->leftchild = NULL;
                (t->leftchild)->rightchild = NULL;
                cout << "Node Added To Left" << endl;
                return;
            }
        }
        else
        {
            if (t->rightchild != NULL)
            {
                insert(t->rightchild, newnode);
            }
            else
            {
                t->rightchild = newnode;
                (t->rightchild)->leftchild = NULL;
                (t->rightchild)->rightchild = NULL;
                cout << "Node Added To Right" << endl;
                return;
            }
        }
    }

    void find(int key, tree **parent, tree **location)
    {
        tree *ptr, *ptrsave;
        if (root == NULL)
        {
            *location = NULL;
            *parent = NULL;
            return;
        }
        if (key == root->data)

        {
            *location = root;
            *parent = NULL;
            return;
        }
        if (key < root->data)
            ptr = root->leftchild;
        else
            ptr = root->rightchild;
        ptrsave = root;
        while (ptr != NULL)
        {
            if (key == ptr->data)
            {
                *location = ptr;
                *parent = ptrsave;
                return;
            }
            ptrsave = ptr;
            if (key < ptr->data)
                ptr = ptr->leftchild;
            else
                ptr = ptr->rightchild;
        }
        *location = NULL;
        *parent = ptrsave;
    }

    void deleteElement(int item)
    {
        tree *parent, *location;
        if (root == NULL)
        {
            cout << "Tree empty" << endl;
            return;
        }
        find(item, &parent, &location);
        if (location == NULL)
        {
            cout << "Item not present in tree" << endl;
            return;
        }
        else
        {
            cout << "Item Deleted"<<endl;
        }
        if (location->leftchild == NULL && location->rightchild == NULL)
        {
            if (parent == NULL)
            {
                root = NULL;
            }
            else
            {
                if (location == parent->leftchild)
                    parent->leftchild = NULL;
                else
                    parent->rightchild = NULL;
            }
        }
        if (location->leftchild != NULL && location->rightchild == NULL)
        {
            tree *child;
            if (location->leftchild != NULL)
                child = location->leftchild;
            else
                child = location->rightchild;
            if (parent == NULL)
            {
                root = child;
            }
            else
            {
                if (location == parent->leftchild)
                    parent->leftchild = child;
                else
                    parent->rightchild = child;
            }

        }
        if (location->leftchild == NULL && location->rightchild != NULL)
        {
            tree *child;
            if (location->leftchild != NULL)
                child = location->leftchild;
            else
                child = location->rightchild;
            if (parent == NULL)
            {
                root = child;
            }
            else
            {
                if (location == parent->leftchild)
                    parent->leftchild = child;
                else
                    parent->rightchild = child;
            }
        }
        if (location->leftchild != NULL && location->rightchild != NULL)
        {

            tree *ptr, *ptrsave, *suc, *parsuc;
            ptrsave = location;
            ptr = location->rightchild;
            while (ptr->leftchild != NULL)
            {
                ptrsave = ptr;
                ptr = ptr->leftchild;
            }
            suc = ptr;
            parsuc = ptrsave;
            if (suc->leftchild == NULL && suc->rightchild == NULL)
            {

                if (parsuc == NULL)
                {
                    root = NULL;
                }
                else
                {
                    if (suc == parsuc->leftchild)
                        parsuc->leftchild = NULL;
                    else
                        parsuc->rightchild = NULL;
                }
            }
            else
            {
                tree *child2;
                if (suc->leftchild != NULL)
                    child2 = suc->leftchild;
                else
                    child2 = suc->rightchild;
                if (parsuc == NULL)
                {
                    root = child2;
                }
                else
                {
                    if (suc == parsuc->leftchild)
                        parsuc->leftchild = child2;
                    else
                        parsuc->rightchild = child2;
                }
            }
            if (parsuc == NULL)
            {
                root = suc;
            }
            else
            {
                if (suc == parsuc->leftchild)
                    parsuc->leftchild = suc;
                else
                    parsuc->rightchild = suc;
            }
            suc->leftchild = suc->leftchild;
            suc->rightchild = suc->rightchild;
        }
        free(location);
    }

    tree* searchElement(tree* temp, int key)
    {
        if ((temp == NULL) || (temp->data == key))
        {
            return temp;
        }
        if (temp->data < key)
        {
            return searchElement(temp->rightchild, key);
        }
        return searchElement(temp->leftchild, key);

    }
    void preorder(tree *t)
    {
        if (root == NULL)
        {
            cout << "Tree is empty" << endl;
            return;
        }
        if (t != NULL)
        {
            cout << t->data << "  ";
            preorder(t->leftchild);
            preorder(t->rightchild);

        }
    }

    void inorder(tree *node)
    {
        if (root == NULL)
        {
            cout << "Tree is empty" << endl;
            return;
        }
        if (node != NULL)
        {
            inorder(node->leftchild);
            cout << node->data << "  ";
            inorder(node->rightchild);
        }
    }

    void postorder(tree * node)
    {
        if (root == NULL)
        {
            cout << "Tree is empty" << endl;
            return;
        }
        if (node != NULL)
        {
            postorder(node->leftchild);
            postorder(node->rightchild);
            cout << node->data << "  ";
        }
    }
    int countNodes(tree *temp)
    {
        if (temp == NULL)
            return 0;
        if (temp->leftchild != NULL)
        {
            n = n + 1;
            n = countNodes(temp->leftchild);
        }
        if (temp->rightchild != NULL)
        {
            n = n + 1;
            n = countNodes(temp->rightchild);
        }
        return n;
    
    }
    int findHeight(tree * temp)
    {
        if (temp == NULL)
        {
            return 0;
        }
        else
        {
            int lb = findHeight(temp->leftchild);
            int rb = findHeight(temp->rightchild);
            return max(lb, rb) + 1;
        }
    }
    
};

int main(int argc, char *argv[])
{
    fstream fin;
    tree* temp;
    BST bstobj;
    temp = new tree;
    
    if (argc != 2)
    {
        cout << "ERROR:  no BST CMD file " << endl;
        return 2;
    }

    
    fin.open(argv[1], ios::in);

    if (!fin.is_open())
    {
        cout << "ERROR: file " << argv[1] << " could not be opened" << endl;
        return 3;
    }

    vector<string> row;
    string line;
    cout << "\n";
    while (getline(fin, line))
    {
        string cmd = "", value = "";
        int flag1 = 0, flag2 = 0;

        for (int i = 0; i < line.length(); i++)
        {
            if (line[i] == ':')
            {
                flag1 += 1;
                continue;
            }
            if (flag1 == 0)
            {
                cmd += line[i];
            }
            else
            {
                value += line[i];
            }
        }
        
        int convertedCmd = 0;
        stringstream t1(cmd);
        t1>>convertedCmd;

        int convertedValue=0;
        stringstream t2(value);
        t2>>convertedValue;
        
        switch (convertedCmd)
        {
        case -1:

            
            cout << "\n\nDelete " << convertedValue << " :\n";
            bstobj.deleteElement(convertedValue);
            
            break;
        case 0: 
            
            exit(0);
            break;
        case 1:
            
            cout << "\nInsert " << convertedValue << "in tree : \n";
            temp = new tree;
            temp->data = convertedValue;
            bstobj.insert(root, temp);
            break;
        case 2:
            cout << endl;
            
            cout << "\nSearch " << convertedValue<<" : \n";
            temp = bstobj.searchElement(root, convertedValue);
            if (temp == NULL)
            {
                cout << convertedValue << " NOT FOUND";
            }
            else
            {
                cout << convertedValue << " Found";
            }
            break;
        case 3:
            cout << "\nPreorder\n";
            bstobj.preorder(root);
            break;
        case 4:
            cout << "\nInorder\n";
            bstobj.inorder(root);
            break;
        case 5:
            cout << "\nPostOrder\n";
            bstobj.postorder(root);
            break;
        case 7:
            cout << "\nNodes is : " << bstobj.countNodes(root);
            n=1;
            break;
        case 8: 
            cout << "\nHeight is : " << bstobj.findHeight(root);
            break;

        default:
            break;
        }
    }
        
        
    
    fin.close();
    
    return 0;
}