#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <stddef.h>

typedef struct node node_t;

struct node {
   node_t *right;
   node_t *left;
   int data;
};

node_t *build_tree(int *tree_data, size_t tree_data_len);
void free_tree(node_t *tree);
int *sorted_data(node_t *tree);

#endif
#include "binary_search_tree.h"


static node_t *create_node(int data) {
    node_t *new_node = (node_t *)malloc(sizeof(node_t));
    if (new_node != NULL) {
        new_node->data = data;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}

static node_t *insert_node(node_t *root, int data) {
    if (root == NULL)
        return create_node(data);

    if (data <= root->data)
        root->left = insert_node(root->left, data);
    else
        root->right = insert_node(root->right, data);

    return root;
}


node_t *build_tree(int *tree_data, size_t tree_data_len) {
    node_t *root = NULL;
    for (size_t i = 0; i < tree_data_len; ++i)
        root = insert_node(root, tree_data[i]);
    return root;
}


void free_tree(node_t *tree) {
    if (tree == NULL)
        return;
    free_tree(tree->left);
    free_tree(tree->right);
    free(tree);
}

static void inorder_traversal(node_t *root, int *result, size_t *index) {
    if (root == NULL)
        return;
    inorder_traversal(root->left, result, index);
    result[(*index)++] = root->data;
    inorder_traversal(root->right, result, index);
}


int *sorted_data(node_t *tree) {
    size_t index = 0;
    int *result = (int *)malloc(sizeof(int) * 1000); 
    if (result != NULL) {
        inorder_traversal(tree, result, &index);
    }
    return result;
}