BinarySearchTree(BasicImplementation)

#include<bits/stdc++.h>

using namespace std;

struct treeNode {
    int item;
    struct treeNode *left;
    struct treeNode *right;
};

struct treeNode *root;


void initializeTree()
{
    root = 0;
}


struct treeNode *makeTreeNode(int item)
{
    struct treeNode *node;
    node = (struct treeNode *)malloc(sizeof(struct treeNode));
    node -> item = item;
    node -> right =0 ;
    node -> left = 0;
    return node;
};


struct treeNode *insertItem(struct treeNode *node, int item)
{
    if(node== 0)
    {
        struct treeNode *newNode = makeTreeNode(item);
        root = newNode;
        return newNode;
    }
    if(node -> item == item)
    {
        return 0;
    }
    if(item < node -> item && node -> left ==0)
    {
        struct treeNode * newNode = makeTreeNode(item);
        node->left = newNode;
        return newNode;
    }
    if(item > node->item && node -> right ==0)
    {
        struct treeNode *newNode = makeTreeNode(item);
        node -> right = newNode;
        return newNode;
    }
    if(item < node ->item)
    {
        return insertItem(node -> left,item);
    }
    else {
        return insertItem(node -> right,item);
    }
};


struct treeNode *searchItem(struct treeNode *node, int item)
{
    if(node ==0)
    {
        return 0;
    }
    if(node -> item == item){
        return node;
    }
    struct treeNode *t = 0;
    if(item < node -> item)
    {
        t = searchItem(node -> left,item);
    }
    else
    {
        t = searchItem(node -> right, item);
    }
};


int calcNodeHeight(struct treeNode *node) ///height of root/full tree
{
    if(node == 0){
        return -1;
    }
    int l , r;
    l = calcNodeHeight(node -> left);
    r = calcNodeHeight(node -> right);
    if(l>r) return l+1;
    else return r+1;
}


int calcHeight(int item){ ///height of a node
    struct treeNode *node = 0;
    node = searchItem(node,item);
    if(node == 0){
        return -1;
    }
    else return calcNodeHeight(node);
}



int calcDepth(int item)//return depth of an item in the tree
{
    struct treeNode *node;
    node = root;
    if(root == 0)
    {
        printf("Insert Something\n");
        return -1;
    }

    struct treeNode *res = searchItem(root,item);
    if(res == 0){
        printf("Not Found\n");
        return -1;
    }


    bool flag ;
    int cnt = 0;
    while(true)
    {

        if(node -> item == item)
        {
           /// flag = true;
            break;
        }
        if(node->item>item)
        {
            node = node ->left;
            cnt++;
        }
        else
        {
            node = node -> right;
            cnt++;
        }
    }
        return cnt;
}


int rangeSearch(struct treeNode *node, int leftbound,int rightbound)
{
    if(root == 0){
    printf("Insert Something\n");
    return -9999;
    }

    if(leftbound == rightbound){
        return 1;
    }

    if(node == 0){
        return 0;
    }

    if(node -> item == leftbound && node -> item == rightbound){
    return 1;
    }

    if(node->item >= leftbound &&  node->item <=rightbound){
        return 1+rangeSearch(node->left,leftbound,rightbound)+rangeSearch(node->right,leftbound,rightbound);
    }

    if(node ->item < rightbound){
        return rangeSearch(node ->left,leftbound,rightbound);
    }

    else {
        return rangeSearch(node->right,leftbound,rightbound);
    }

}

/**struct treeNode *GetMinNode(struct treeNode *node){
    if(node == 0){
        return 0;
    }

    else {
        return
    }


    /**while(node->left!=0){
        node = node ->left;
    }*/
    /*return node;
};*/



int deleteItem(struct treeNode *node, int item){

    int n;
    struct treeNode *temp = searchItem(root,item);
    if(temp == 0){
        printf("Not Found\n");
        return -9999;
    }
    struct treeNode *cur = node;
    struct treeNode *prev=cur;
    if(cur == 0){
        ///printf("Insert Something\n");
        return 0;
    }

    while(true){
        ///if(node)

        if(cur-> item == item)
        {
           /// flag = true;
            break;
        }
        if(cur->item >item)
        {
            prev = cur;
            cur= cur ->left;
           /// cnt++;
        }
        else
        {
            prev = cur;
            cur = cur -> right;
           /// cnt++;
        }
    }
    bool flag = false;
    if (cur == root){
        flag = true;
    }

    if(cur-> left == 0 && cur->right==0 ){

        if(flag){
            ///root = 0;
            free(cur);
            root = 0;
            return 1;
        }


        if(prev -> right == cur){

           /// cout<<"prev -> right == cur"<<endl;
            prev -> right = 0;
        }
        else {
            ///cout<<"prev -> left"<<endl;
            prev -> left = 0;
        }
        free(cur);
        ///cur = 0;
        return 1;
    }


    else if(cur -> left == 0){
        ///struct treeNode *t;
        ///t = cur->right;
       /// t->left = res->left;
       if(flag){
        root = cur -> right;
        free(cur);
        return 1;
       }


       if(prev -> left == cur){
        prev -> left = cur -> left;
       }
       else
       {
           prev -> right = cur -> right;
       }
       free(cur);


        ///free(cur);
        return 1;
    }
    if(cur -> right ==0){
        if(flag){
            root = cur -> left;
            free(cur);
            return 1;
        }


        if(prev -> right == cur){
            prev -> right = cur -> left;
        }
        else {
            prev -> left = cur -> left;
        }
        free(cur);
        return 1;
    }
    else
    {
        struct treeNode *t,*t1;
        t = cur->right;
        while(t->left!=0){

            t = t->left;
        }

       /// temp = GetMinNode(cur ->right);
        if(flag)
        {
            /*struct treeNode *n;
            n= t;*/
           /// root = t;
           //cout<<"t -> item "<<t->item<<endl;
            cur -> item = t->item;
            ///root = cur;
            ///if(prev == t)
            prev->right = prev ->right ->right;

            //else
            //prev->left = t->right;
            ///cur -> right = prev->right;
            free(t);

            //cout<<"root item -> "<<root -> item<<endl;
           // delete t;
           /// free(n);
            return 1;
        }
        if(prev -> right == cur){
            prev -> right = t;
        }
        else {
            prev -> left = t;
        }
        free(cur);
        return 1;
    }

}



void printInOrder(struct treeNode * node, int height)
{
    if(node==0) return  ;

    //print left sub-tree
    printInOrder(node->left, height-1);

    //print item
    for(int i=0;i<height;i++)printf("   ");
    printf("%03d\n",node->item);

    //print right sub-tree
    printInOrder(node->right, height-1);
}


int getSize(struct treeNode *node)
{
    if(node == 0)
    {
        return 0;
    }
    return 1+getSize(node -> left)+getSize(node->right);
}

int getMinItem()
{
    struct treeNode *node;
    node = (struct treeNode *)malloc(sizeof(treeNode));
    node = root;
    if(root==0) return -99999;
    else
    {
        while(node->left!=0){
            node = node->left;
        }
    }
    int value = node->item;
    return value;
}


int getMaxItem()
{
    struct treeNode *node;
    node = (struct treeNode *)malloc(sizeof(treeNode));
    node = root;
    if(root==0) return -99999;
    else
    {
        while(node->right!=0){
            node = node->right;
        }
    }
    int value = node->item;
    return value;
}



int calcNodeDepth(struct treeNode *node)
{
    int item = node -> item;
    return calcDepth(item);
}



int main()
{
    ios_base::sync_with_stdio(false);
    initializeTree();
    while(1)
    {
        printf("1. Insert item. 2. Delete item. 3. Search item. \n");
        printf("4. Print height of tree. 5. Print height of an item. \n");
        printf("6. PrintInOrder. 7. exit. 8.GetSize Of the tree \n");
        printf("9. GetMinValue. 10. GetMaxValue. 11. Calc Depth Of an Item\n");
        printf("12. Range Search \n");

        int ch;
        scanf("%d",&ch);
        if(ch==1)
        {
            int item;
            scanf("%d", &item);
            insertItem(root, item);
        }
        else if(ch==2)
        {
            int item;
            scanf("%d", &item);
            deleteItem(root, item);
        }
        else if(ch==3)
        {
            int item;
            scanf("%d", &item);
            struct treeNode * res = searchItem(root, item);
            if(res!=0) printf("Found.\n");
            else printf("Not found.\n");
        }
        else if(ch==4)
        {
            int height = calcNodeHeight(root);
            printf("Height of tree = %d\n", height);
        }
        else if(ch==5)
        {
            int item;
            scanf("%d", &item);
            int height = calcHeight(item);
            printf("Height of %d = %d\n", item, height);
        }
        else if(ch==6)
        {
            int h = calcNodeHeight(root);
            printf("\n--------------------------------\n");
            printInOrder(root, h);
            printf("--------------------------------\n");
        }
        else if(ch==7)
        {
            break;
        }
        else if(ch==8){
            int n = getSize(root);
            printf("Size -> %d\n",n);
        }
        else if(ch==9){
            int n = getMinItem();
            printf("Min Item -> %d\n",n);
        }
        else if(ch==10){
            int n = getMaxItem();
            printf("Max item -> %d\n",n);
        }
        else if(ch==11){
                int item;
                scanf("%d",&item);
            int n = calcDepth(item);
            printf("Depth -> %d\n",n);
        }
        else if(ch==12){
            int low,high;
            scanf("%d %d",&low,&high);
            int n = rangeSearch(root,low,high);
            printf("total element within this range -> %d\n",n);
        }
    }
    return 0;
}