#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <conio.h>
#include <vector>
#include <iostream> 
#include "ConsoleApplicationTrash8.h"
#include <queue>
using namespace std;
using std::cout; using std::cin;
using std::endl; using std::string;
using std::vector;

#define CMP_EQ(a, b) ((a) == (b))
#define CMP_LT(a, b) ((a) < (b))
#define CMP_GT(a, b) ((a) > (b))

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

int getSize() {
    int ind;
    int size;
    int flag;
    do {
        do {
            rewind(stdin);
            printf("Enter the size of the list\n");
            ind = scanf_s("%d", &size);
            if (ind != 1) {
                printf("Incorrect input!!!\n");
            }
        } while (ind != 1);
        if ((size > 20) || (size < 1))
        {
            printf("Enter the size between 1 and 20");
            flag = 1;
        }
        else {
            flag = 0;
        }
    } while (flag == 1);
    return size;
}

int getNumber(int i) {
    int ind;
    int num;
    int flag;
    do {
        do {
            rewind(stdin);
            printf("Enter element number %d: ", i + 1);
            ind = scanf_s("%d", &num);
            if (ind != 1) {
                printf("Incorrect input!!!\n");
            }
        } while (ind != 1);
        if ((num > 50) || (num < -50))
        {
            printf("Enter the number, which is higher than -50 and lower than 50\n");
            flag = 1;
        }
        else {
            flag = 0;
        }
    } while (flag == 1);
    return num;
}


Node* getFreeNode(int value) {
    Node* tmp = (Node*)malloc(sizeof(Node));
    tmp->left = tmp->right = NULL;
    tmp->data = value;
    return tmp;
}

void insert(Node** head, int value) {
    Node* tmp = NULL;
    Node* ins = NULL;
    int lvl = 1;
    if (*head == NULL) {
        *head = getFreeNode(value);
        return;
    }

    tmp = *head;
    while (tmp) {
        if (CMP_GT(value, tmp->data)) {
            if (tmp->right) {
                tmp = tmp->right;
                lvl++;
                continue;
            }
            else {
                tmp->right = getFreeNode(value);
                return;
            }
        }
        else if (CMP_LT(value, tmp->data)) {
            if (tmp->left) {
                tmp = tmp->left;
                lvl++;
                continue;
            }
            else {
                tmp->left = getFreeNode(value);
                return;
            }
        }
        else {
            exit(2);
        }
    }
}

Node* getNodeByValue(Node* root, int value) {
    while (root) {
        if (CMP_GT(root->data, value)) {
            root = root->left;
            continue;
        }
        else if (CMP_LT(root->data, value)) {
            root = root->right;
            continue;
        }
        else {
            return root;
        }
    }
    return NULL;
}

Node * getMaxNode(Node * root) {
    while (root->right) {
        root = root->right;
    }
    return root;
}

void inorder(Node* root)
{
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

Node* insert(Node* node, int key)
{
    if (node == NULL)
        return getFreeNode(key);
    if (key < node->data)
        node->left = insert(node->left, key);
    else
        node->right = insert(node->right, key);
    return node;
}

Node* minValueNode(Node* node)
{
    Node* current = node;
    while (current && current->left != NULL)
        current = current->left;

    return current;
}

Node* deleteNode(Node* root, int key)
{
    if (root == NULL)
        return root;
    if (key < root->data)
        root->left = deleteNode(root->left, key);
    else if (key > root->data)
        root->right = deleteNode(root->right, key);
    else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

int findDigits(int num) {
    int n = 0;
    while (num != 0) {
        num = num / 10;
        n++;
    }
    return n;
}

int findHeight(Node* root) {
    if (root == nullptr) return 0;
    return std::max(findHeight(root->left), findHeight(root->right)) + 1;
}

void visualise(Node* root) {
    if (root == nullptr) return;
    int height = findHeight(root);
    std::queue<Node*> n;
    std::queue<Node*> e;
    n.push(root);
    int i;
    int digits = 1;
    Node* temp = nullptr;
    for (int level = 0; level < height; level++) {
        temp = n.front();
        e.push(n.front());
        n.pop();
        for (i = 0; i < pow(2, height - level) - 2; i++) std::cout << " ";

        if (temp != nullptr) std::cout << temp->data;
        else std::cout << " ";
        for (int k = 1; k < pow(2, level); k++) {
            if (temp != NULL) digits = findDigits(temp->data);
            temp = n.front();
            e.push(n.front());
            n.pop();
            for (i = 0; i < pow(2, height + 1 - level) - digits; i++) std::cout << " ";
            digits = 1;
            if (temp != nullptr) std::cout << temp->data;
            else std::cout << " ";
        }

        for (i = 0; i < pow(2, height - level) - 2; i++) std::cout << " ";
        std::cout << "\n";

        if (level != height - 1) {
            for (i = 0; i < (pow(2, height - level) - 2 - pow(2, height - level - 2)); i++) std::cout << " ";

            for (int k = 0; k < pow(2, level); k++) {
                temp = e.front();
                if (temp == NULL) temp = new Node();
                n.push(temp->left);
                if (temp->left != NULL) std::cout << "/";
                else std::cout << " ";
                for (i = 0; i < pow(2, height - level - 1) - 1; i++) std::cout << " ";
                n.push(temp->right);
                if (temp->right != NULL) std::cout << "\\";
                else std::cout << " ";
                for (i = 0; i < (pow(2, height - level + 1) - 1 - pow(2, height - level - 1)); i++) std::cout << " ";
                e.pop();
            }

            for (i = 0; i < (pow(2, height - level) - 2 - pow(2, height - level - 2)); i++) std::cout << " ";
            std::cout << "\n";
        }
    }
}

void main() {
    Node* root = NULL;
    int size = 0;
    int num = 0;
    size = getSize();
    for (int i = 0; i < size; i++) {
        num = getNumber(i);
        insert(&root, num);
    }
    visualise(root);
    printf("Max node is %d\n", getMaxNode(root)->data);
    deleteNode(root, 2);
    visualise(root);
}