Untitled

#include <stdio.h>
#include <math.h>

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* node, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* node2 = node->right;

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

    if(parent != NULL){
        if(parent->right == node){
            parent->right = node2;
        } else {
            parent->left = node2;
        }
    }

    return node2;
}


struct BinarySerchTreeNode* singleRotationLeft(struct BinarySerchTreeNode* node9, struct BinarySerchTreeNode* parent){
    struct BinarySerchTreeNode* node8 = node9->left;

    node8->right = node9;
    node9->left = NULL;

    if(parent != NULL){
        if(parent->left == node9){
            parent->left = node8;
        } else {
            parent->right = node8;
        }
    }

    return node8;
}

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;
    data->height = 0;

    return node;
};

struct BinarySerchTreeNode* insertN1(int data, struct BinarySerchTreeNode* node, struct BinarySerchTreeNode* parent){
    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(node->left->right == NULL){
                singleRotationLeft(node, parent);
            } else {
                //doubleRotation(node, parent);
            }
        }
    }
    else if(data > node->data){
        node->right = insertN(data,node->right, node);
        

    }

    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);


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

    tree2 = singleRotation1left(tree2, NULL);





    return 0;
}