#include "binary_search_tree.h"
#include <stdlib.h>
#include <string.h>

int count_nodes(node_t *tree);
void in_order_traversal(node_t *tree, int **ptr);

node_t *build_tree(int *tree_data, size_t tree_data_len) {
    if (tree_data_len == 0) {
        return NULL;
    }

    node_t *root = malloc(sizeof(node_t));
    root->data = tree_data[0];
    root->left = NULL;
    root->right = NULL;

    for (size_t i = 1; i < tree_data_len; i++) {
        node_t *current = root;
        node_t *parent = NULL;

        while (current!= NULL) {
            parent = current;
            if (tree_data[i] < current->data) {
                current = current->left;
            } else {
                current = current->right;
}
        }

        current = malloc(sizeof(node_t));
        if (current == NULL) {
            free_tree(root);
            return NULL;
        }
        current->data = tree_data[i];
        current->left = NULL;
        current->right = NULL;

        if (tree_data[i] < parent->data) {
            parent->left = current;
        } else {
            parent->right = current;
        }
    }

    return root;
}

void free_tree(node_t *tree) {
    if (tree == NULL) {
        return;
    }

    free_tree(tree->left);
    free_tree(tree->right);
    free(tree);
}

int *sorted_data(node_t *tree) {
    int *data = malloc(sizeof(int) * count_nodes(tree));
    int *ptr = data;
    in_order_traversal(tree, &ptr);
    return data;
}

int count_nodes(node_t *tree) {
    if (tree == NULL) {
        return 0;
    }

    return 1 + count_nodes(tree->left) + count_nodes(tree->right);
}

void in_order_traversal(node_t *tree, int **ptr) {
    if (tree == NULL) {
        return;
    }

    in_order_traversal(tree->left, ptr);
    **ptr = tree->data;
    (*ptr)++;
    in_order_traversal(tree->right, ptr);
}