Untitled

#include <stdio.h>
#include <math.h>
struct BinarySerchTreeNode* insertInNonRecursiveWay(int x, struct BinarySerchTreeNode* node);
struct BinarySerchTreeNode{
    int data;
    int height;
    struct BinarySerchTreeNode* left; //left child
    struct BinarySerchTreeNode* right; //right child
};


struct BinarySerchTreeNode* singleRotation(struct BinarySerchTreeNode* node){
    struct BinarySerchTreeNode* node2 = node->right;

    node2->left = node;
    node->right = NULL;

    return node2;
}

struct BinarySerchTreeNode* singleRotationRight(struct BinarySerchTreeNode* k1, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* k2 = k1->right;

    k1->right = k2->left;
    k2->left = k1;

    if(parent != NULL){
        if(parent->right == k1){
            parent->right = k2;
        } else {
            parent->left = k2;
        }
    }

    k1->height = findMax(getHeight1(k1->left),getHeight1(k1->right)) + 1;
    k2->height = findMax(getHeight1(k2->left),getHeight1(k2->right)) + 1;

    return k2;
}


struct BinarySerchTreeNode* singleRotationLeft(struct BinarySerchTreeNode* k2, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* k1 = k2->left;

    k2->left = k1->right;
    k1->right = k2;

    if(parent != NULL){
        if(parent->left == k2){
            parent->left = k1;
        } else {
            parent->right = k1;
        }
    }

    k2->height = findMax(getHeight1(k2->left),getHeight1(k2->right)) + 1;
    k1->height = findMax(getHeight1(k1->left),getHeight1(k1->right)) + 1;


    return k1;
}


struct BinarySerchTreeNode* doubleRotationLeft(struct BinarySerchTreeNode* node, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* k3 = node;
    struct BinarySerchTreeNode* k1 = k3->left;
    struct BinarySerchTreeNode* k2 = k1->right;
    struct BinarySerchTreeNode* B = k2->left;
    struct BinarySerchTreeNode* C = k2->right;

    k2->left = k1;
    k2->right = k3;
    k1->right = B;
    k3->left = C;

    if(parent != NULL){
        if(parent->right == k3){
            parent->right = k2;
        } else {
            parent->left = k2;
        }
    }

    k1->height = findMax(getHeight1(k1->left),getHeight1(k1->right)) + 1;
    k3->height = findMax(getHeight1(k3->left),getHeight1(k3->right)) + 1;

    k2->height = findMax(getHeight1(k2->left),getHeight1(k2->right)) + 1;

    return k2;
}


struct BinarySerchTreeNode* doubleRotationRight(struct BinarySerchTreeNode* node, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* k3 = node;
    struct BinarySerchTreeNode* k1 = k3->right;
    struct BinarySerchTreeNode* k2 = k1->left;
    struct BinarySerchTreeNode* B = k2->left;
    struct BinarySerchTreeNode* C = k2->right;

    k2->left = k3;
    k2->right = k1;
    k3->right = B;
    k1->left = C;

    if(parent != NULL){
        if(parent->right == k3){
            parent->right = k2;
        } else {
            parent->left = k2;
        }
    }

    k1->height = findMax(getHeight1(k1->left),getHeight1(k1->right)) + 1;
    k3->height = findMax(getHeight1(k3->left),getHeight1(k3->right)) + 1;

    k2->height = findMax(getHeight1(k2->left),getHeight1(k2->right)) + 1;



    return k2;


}

int heightDifference(struct BinarySerchTreeNode* node){
    // 2 0 = 2-0 = 2
    // 1 1 = 1-1 = 0
    // 1 2 = 2-1 = 1

    int leftHeight = height(node->left);
    int rightHeight = height(node->right);

    int heightDifference1 = leftHeight - rightHeight;
    return abs(heightDifference1);


/*
    if(leftHeight > rightHeight){
        return leftHeight - rightHeight;
    } else {
        return rightHeight - leftHeight;
    }
*/
}

int height(struct BinarySerchTreeNode* node){
    if(node == NULL) return -1;

    //printf("we are calculating the height of %d\n", node->data);

    //if(node->left == NULL && node->right ==NULL) {
    //    height  = 0;
    //}

    int leftHeight = height(node->left); //2
    int rightHeight = height(node->right); //1

    int height = findMax(leftHeight, rightHeight);

    //printf("calculation of height for node %d is completed\n ", node->data);
    return height+1;

};

int findMax(int a, int b){
    if(a > b){
        return a;
    } else {
        return b;
    }
}

struct BinarySerchTreeNode* addData(int data){
    struct BinarySerchTreeNode* node =  malloc(sizeof(struct BinarySerchTreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->height = 0;

    return node;
};

struct BinarySerchTreeNode* insertN1(int data, struct BinarySerchTreeNode* node, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* rotatedTree;
    if(node == NULL){
        node = addData(data);
    }
    else if(data < node->data){
        node->left = insertN1(data,node->left, node);

        if(getHeight1(node->left) - getHeight1(node->right) == 2){
            if(data < node->left->data){
                 rotatedTree = singleRotationLeft(node, parent);
            } else {
                rotatedTree = doubleRotationLeft(node, parent);
            }
            return rotatedTree;
        }
    }
    else if(data > node->data){
        node->right = insertN1(data,node->right, node);
        if(getHeight1(node->right) - getHeight1(node->left) == 2){
            if(data > node->right->data){
                rotatedTree = singleRotationRight(node, parent);
            } else {
                rotatedTree = doubleRotationRight(node, parent);
            }

            return rotatedTree;
        }

    }

    node->height = findMax(getHeight1(node->left), getHeight1(node->right)) + 1;

    return node;

}


struct BinarySerchTreeNode* insertN(int data, struct BinarySerchTreeNode* node){
    insertN1(data, node, NULL);
}





int getHeight1(struct BinarySerchTreeNode* node){
    if(node == NULL){
        return -1;
    } else {
        return node->height;
    }
}



struct BinarySerchTreeNode* makeTree(){
    struct BinarySerchTreeNode* root = insertN(6, NULL);
    insertN(2, root);
    insertN(8, root);
    insertN(1, root);
    insertN(4, root);
    insertN(3, root);

    return root;
}

struct BinarySerchTreeNode* findMin(struct BinarySerchTreeNode* node){
    if(node == NULL){
        return NULL;
    }
    else if(node->left == NULL){
        return (node);
    }
    else {
        return(findMin(node->left));
    }
}

struct BinarySerchTreeNode* deleteN(int data, struct BinarySerchTreeNode* node){
    struct BinarySerchTreeNode* deleteStore;
    struct BinarySerchTreeNode* child;
    if(node == NULL){

    }
    else if(data < node->data){
        printf("%d -> ", node->data);
        node->left = deleteN(data,node->left);

    }
    else if(data > node->data){
        printf("%d -> ", node->data);
        node->right = deleteN(data,node->right);
    }
    else if(node->left != NULL && node->right != NULL){
        printf("reached node %d ->", node->data);
        printf("finding the minimum node in right sub tree -> ");
        deleteStore = findMin(node->right);
        printf(" replacing %d with %d -> ", node->data, deleteStore->data);
        node->data = deleteStore->data;
        node->right = deleteN(node->data,node->right);

    }
    else{
        deleteStore = node;
        if(node->left == NULL){
            child = node->right;
        }
        else if(node->right == NULL){
            child = node->left;
        }
        printf(" deleting %d", node->data);

        free(deleteStore);

        return child;
    }
    return node;
}

void inOrderTraversal(struct BinarySerchTreeNode* node){
    if(node == NULL) return;

    inOrderTraversal(node->left);
    printf("%d ", node->data);
    inOrderTraversal(node->right);
}

int main(){
    /*
    struct BinarySerchTreeNode* root = insertN(1, NULL);
    insertN(2, root);
    insertN(3, root);

    root = singleRotationRight(root, NULL);
    struct BinarySerchTreeNode* node2 = root;

    struct BinarySerchTreeNode* node3 = root->right;
    insertN(4, root);
    struct BinarySerchTreeNode* node4 = node3->right;
    insertN(5, root);
    struct BinarySerchTreeNode* node5 = node4->right;

    int height5 = heightDifference(node5);
    int height4 = heightDifference(node4);
    int height3 = heightDifference(node3);


    printf("%d %d %d", height5,height4, height3);

    struct BinarySerchTreeNode* node = singleRotationRight(node3, node2);
    printf("\n%d", node->data);




    printf("========================");

    struct BinarySerchTreeNode* nodea = malloc(sizeof(struct BinarySerchTreeNode));
    struct BinarySerchTreeNode nodeb = *nodea;
    nodeb.data = 3;

    printf("saiofhnsid: %d\n", nodeb.data);
    printf("========================");

    struct BinarySerchTreeNode* tree2 = insertN(9, NULL);
    insertN(8, root);
    insertN(7, root);

    //tree2 = singleRotation1left(tree2, NULL);
*/
    printf("=================================abc\n");

    struct BinarySerchTreeNode* dnode1 = insertInNonRecursiveWay(8, NULL);
    insertInNonRecursiveWay(10, dnode1);
    insertInNonRecursiveWay(9, dnode1);

    dnode1 = doubleRotationRight(dnode1, NULL);
    printf("%d %d %d", dnode1->data, dnode1->left->data, dnode1->right->data);

    printf("=================================abc\n");

    struct BinarySerchTreeNode* dnode2 = insertInNonRecursiveWay(8, NULL);
    insertInNonRecursiveWay(6, dnode2);
    insertInNonRecursiveWay(7, dnode2);

    dnode2 = doubleRotationLeft(dnode2, NULL);
    printf("%d %d %d", dnode2->data, dnode2->left->data, dnode2->right->data);

    printf("\nstarting insertN function =================================\n");
    struct BinarySerchTreeNode* inode1 = insertN(1, NULL);
    inode1 = insertN(2, inode1);
    inode1 = insertN(3, inode1);
    printf("%d", inode1->data);
    printf("\n%d", inode1->height);
    inode1 = insertN(4, inode1);
    inode1 = insertN(5, inode1);
    printf("\n%d", inode1->right->data);
    printf("\n%d", inode1->right->left->data);
    inode1 = insertN(6, inode1);
    printf("\n%d", inode1->data);
    inode1 = insertN(7, inode1);
    inode1 = insertN(15, inode1);
    inode1 = insertN(14, inode1);
    printf("\n%d", inode1->right->right->data);
    printf("\n%d", inode1->right->data);
    inode1 = insertN(13, inode1);
    printf("\n%d", inode1->right->data);
    inode1 = insertN(12, inode1);
    printf("\n%d", inode1->data);
    return 0;
}

struct BinarySerchTreeNode* insertInNonRecursiveWay(int x, struct BinarySerchTreeNode* node){
    if(node == NULL){
        return addData(x);
    }

    struct BinarySerchTreeNode* node1 = node;

    while(node1 != NULL){
        if(x < node1->data){
            if(node1->left == NULL){
                node1->left = addData(x);
                return node;
            } else {
                node1 = node1->left;
            }

        } else if(x > node1->data){
            if(node1->right == NULL){
                node1->right = addData(x);
                return node;
            } else {
                node1 = node1->right;
            }
        } else {
            return node;
        }
    }
}