#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct node {
    int data;
    struct node *left_child, *right_child;
};

struct node* newNode(int val);
struct node* insert(struct node* root, int data);

struct node* minValueNode(struct node* root);
struct node* deleteNode(struct node* root, int data);

void printLevelOrder(struct node* root);
void printGivenLevel(struct node* root, int level);
int height(struct node* root);

void printPreOrder(struct node* root);
void printInOrder(struct node* root);
void printPostOrder(struct node* root);


int countNodes(struct node* root);
bool checkCompleteBinaryTree (struct node* root, int index, int number_nodes);

void printMaxHeight(int val);

int main(){
    int ch;
    struct node* root = NULL;

    while (1){
        printf("\n\tMENU\n");
        printf("\n1. Insert into tree");
        printf("\n2. Delete from tree");
        printf("\n3. Print binary search tree Level order");
        printf("\n4. Print binary search tree Preorder");
        printf("\n5. Print binary search tree Inorder");
        printf("\n6. Print binary search tree Postorder");
        printf("\n7. Check if binary search tree is complete");
        printf("\n8. Print BST at height");
        printf("\n9. Exit\n>> ");
        scanf("%d", &ch);
        int val, flag;
        switch (ch){
            case 1:
                printf("\nEnter value: ");
                scanf("%d", &val);
                root = insert(root, val);
                printf("\nInserted\n");
                printf("\nInOrder: ");
                printInOrder(root);
                break;
            case 2:
                printf("\nEnter value to delete: ");
                scanf("%d", &val);
                root = deleteNode(root, val);
                printf("\nInOrder: ");
                printInOrder(root);
                break;
            case 3:
                printf("\nLevel Order: ");
                printLevelOrder(root);
                printf("\n");
                break;
            case 4:
                printf("\nPreOrder: ");
                printPreOrder(root);
                printf("\n");
                break;
            case 5:
                printf("\nInOrder: ");
                printInOrder(root);
                printf("\n");
                break;
            case 6:
                printf("\nPostOrder: ");
                printPostOrder(root);
                printf("\n");
                break;
            case 7:
                if (checkCompleteBinaryTree(root, 0, countNodes(root))){
                    printf("The Binary Tree is complete\n");
                }
                else{
                    printf("The Binary Tree is not complete\n");
                }
                break;
            case 8:
                printf("\nEnter the height: ");
                scanf("%d", &val);
                printMaxHeight(val);
                break;
            case 9:
                exit(0);
            default:
                printf("\nInvalid option\n");
        }
    }
    return 0;
}

struct node* newNode(int val){
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    temp->data = val;
    temp->left_child = temp->right_child = NULL;
    return temp;
}

struct node* insert(struct node* root, int data){
    if (root == NULL){
        return newNode(data);
    }

    if (data < root->data){
        root->left_child = insert(root->left_child, data);
    }
    else{
        root->right_child = insert(root->right_child, data);
    }
    return root;
}

struct node* minValueNode(struct node* root){
    struct node* current = root;

    while (current && current->left_child != NULL){
        current = current->left_child;
    }
    return current;
}

struct node* deleteNode(struct node* root, int data){

    if (root == NULL){
        return root;
    }

    if (data < root->data){
        root->left_child = deleteNode(root->left_child, data);
    }
    else if (data > root->data){
        root->right_child = deleteNode(root->right_child, data);
    }
    else {
        if (root->left_child == NULL) {
            struct node* temp = root->right_child;
            free(root);
            return temp;
        }
        else if (root->right_child == NULL) {
            struct node* temp = root->left_child;
            free(root);
            return temp;
        }

        struct node* temp = minValueNode(root->right_child);
        root->data = temp->data;
        root->right_child = deleteNode(root->right_child, temp->data);
    }
    return root;
}


int height(struct node* root){
    if (root == NULL){
        return 0;
    }
    else{
        int lheight = height(root->left_child);
        int rheight = height(root->right_child);

        if (lheight > rheight){
            return (lheight + 1);
        }
        else{
            return (rheight  + 1);
        }
    }
}

void printGivenLevel(struct node* root, int level){
    if (root == NULL){
        return ;
    }
    if (level == 1){
        printf("%d ", root->data);
    }
    else if (level > 1){
        printGivenLevel(root->left_child, level-1);
        printGivenLevel(root->right_child, level-1);
    }
}

void printLevelOrder(struct node* root){
    int h = height(root);
    int i;
    for (i = 1; i <= h; i++){
        printGivenLevel(root, i);
    }
}

void printPreOrder(struct node* root){
    // root, left_child, right_child
    if (root != NULL){
        printf("%d ", root->data);
        printPreOrder(root->left_child);
        printPreOrder(root->right_child);
    }
}

void printInOrder(struct node* root){
    // left_child, root, right_child
    if (root != NULL){
        printInOrder(root->left_child);
        printf("%d ", root->data);
        printInOrder(root->right_child);
    }
}

void printPostOrder(struct node* root){
    // left_child, right_child, root
    if (root != NULL){
        printPostOrder(root->left_child);
        printPostOrder(root->right_child);
        printf("%d ", root->data);
    }
}

void printMaxHeight(int val){
    int max_height = val - 1;
    printf("\nThe max height is %d", max_height);
}

int countNodes(struct node* root)
{
    if (root == NULL)
        return (0);
    return (1 + countNodes(root->left_child) + countNodes(root->right_child));
}

bool checkCompleteBinaryTree (struct node* root, int index, int number_nodes)
{
    // An empty tree is complete
    if (root == NULL)
        return (true);

    // If index assigned to current node is more than
    // number of nodes in tree, then tree is not complete
    if (index >= number_nodes)
        return (false);

    // Recur for left and right subtrees
    return (checkCompleteBinaryTree(root->left_child, 2*index + 1, number_nodes) &&
    checkCompleteBinaryTree(root->right_child, 2*index + 2, number_nodes));
}