#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//#include <unistd.h>
#include "bst.h"

typedef enum { false, true } bool;

Node* findMinimum(Node* root)
{
    if (root == NULL)
        return NULL;
    else if (root->left != NULL)
        return findMinimum(root->left); // left most element will be minimum
    return root;
}

Node* createNode(int value) {
    Node* n;
    n = malloc(sizeof(struct Node)); // Allocate memory for new node
    n->data = value;
    n->left = NULL;
    n->right = NULL;
    return n;
}

Node* insertNode(Node* root, int value) {
    if (root == NULL) { // If tree is empty
        return createNode(value);
    }
    else if (value < root->data) { // If we need to follow the left branch
        root->left = insertNode(root->left, value);
    }
    else if (value > root->data) { // If we need to follow the right branch
        root->right = insertNode(root->right, value);
    }
    return root;
}

Node* deleteNode(Node* root, int value) {
    if (root == NULL)
        return NULL;

    if (value > root->data)
        root->right = deleteNode(root->right, value);
    else if (value < root->data)
        root->left = deleteNode(root->left, value);
    else {
        // If we're deleting a leaf node
        if (root->left == NULL && root->right == NULL)
        {
            free(root);
            return NULL;
        }
        // If we're deleting a node with ONE child
        else if (root->left == NULL || root->right == NULL) {
            Node* temp;
            if (root->left == NULL) { // The child node exists in the right branch
                temp = root->right;
                free(root);
                return temp;
            }
            else { // The child node exists in the left branch
                temp = root->left;
                free(root);
                return temp;
            }
        }
        // If we're deleting a node with TWO children
        else {
            Node* temp = findMinimum(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    return root;
}

void printSubtree(Node* N) {
    if (N != NULL) // Ensuring we dont try to print a nullptr
    {
        printSubtree(N->left); // Print all left child nodes
        printf("%d\n", N->data); // Print the root
        printSubtree(N->right);// Print all right child nodes
    }
}

int countNodes(Node* N) {
    int nodes = 1;
    if (N != NULL) {
        nodes += countNodes(N->left);
        nodes += countNodes(N->right);
        return nodes;
    }
    else
        return 0;
}

Node* freeSubtree(Node* N) {
    if (N != NULL) {
        freeSubtree(N->left);
        freeSubtree(N->right);
        free(N);
    }
    return NULL;
}


int sumSubtree(Node *N)
{
    if (N != NULL)
    {
        return N->data + sumSubtree(N->left) + sumSubtree(N->right);
    }
    else
        return 0;

}

void traverse_tree(Node* root, Node** ordered_nodes, size_t* index) {
    if (root) {
        traverse_tree(root->left, ordered_nodes, index);
        ordered_nodes[(*index)++] = root;
        traverse_tree(root->right, ordered_nodes, index);
    }
}

Node* rebuild_tree(Node** ordered_nodes, size_t left, size_t right) {
    size_t mid;

    if (left <= right) {
        mid = (left + right) / 2;
        if (mid > 0) {
            ordered_nodes[mid]->left = rebuild_tree(ordered_nodes, left, mid - 1);
        }
        ordered_nodes[mid]->right = rebuild_tree(ordered_nodes, mid + 1, right);
        return ordered_nodes[mid];
    }
    else {
        return NULL;
    }
}

// This functions converts an unbalanced BST to a balanced BST
Node* balanceTree(Node* root)
{
    size_t   count = 0;
    Node** ordered_nodes = NULL;
    Node* result = NULL;

    count = countNodes(root);
    ordered_nodes = (Node**)malloc(sizeof(Node*) * count);
    count = 0;
    traverse_tree(root, ordered_nodes, &count);
    result = rebuild_tree(ordered_nodes, 0, count - 1);
    free(ordered_nodes);
    return result;
}