I'm working on implementing a binary search tree data structure in C using an array. I understand the concept of a tree, but having some trouble implementing it as you may notice from my code. I'm getting stuck on some of the functions so feel free to edit any of the functions, even the ones I filled, without changing the parameters nor adding/removing any functions. All helpful replies will be upvoted of course.

HEADER FILE: #ifndef TREE_H #define TREE_H

#include

// The type for a node in the tree. struct node { int value; struct node *left_child; struct node *right_child; };

// The type for the tree. typedef struct node BSTree;

// The type for a tree position. typedef struct node* BSTreePos;

// Create and return a binary search tree with the value in a root-node. BSTree *bs_tree_make(int value);

// Insert a node with the value as the left child to the node with position pos. BSTreePos bs_tree_insert_left(int value, BSTreePos pos);

// Insert a node with the value as the right child to the node with position pos. BSTreePos bs_tree_insert_right(int value, BSTreePos pos);

// Get the value at the position. int bs_tree_inspect_label(BSTreePos pos);

// Check if the node at the position has a left child. bool bs_tree_has_left_child(BSTreePos pos);

// Check if the node at the position has a right child. bool bs_tree_has_right_child(BSTreePos pos);

// Get the position of the root. BSTreePos bs_tree_root(BSTree *tree);

// Get the position of the left child to the node with position pos. BSTreePos bs_tree_left_child(BSTreePos pos);

// Get the position of the right child to the node with position pos. BSTreePos bs_tree_right_child(BSTreePos pos);

// Deallocate the binary search tree. void bs_tree_destroy(BSTree *tree);

#endif /* TREE_H */

MAIN FILE:

#include "tree.h" #include #include #include

// Create and return a binary search tree with the value in a root-node. BSTree *bs_tree_make(int value){ // Allocate memory for new node struct node* origin = (struct node*)malloc(sizeof(struct node));

// Assign data to this node origin->data = value;

// Initialize left and // right children as NULL origin->left_child = NULL; origin->right_child = NULL; return (origin); }

// Insert a node with the value as the left child to the node with position pos. BSTreePos bs_tree_insert_left(int value, BSTreePos pos){ pos->left_child = bs_tree_make(value); return pos->left_child; }

// Insert a node with the value as the right child to the node with position pos. BSTreePos bs_tree_insert_right(int value, BSTreePos pos){ struct node *temp = malloc(sizeof(struct node)); pos->right_child = bs_tree_make(value); return pos->right_child; }

// Get the value at the position. int bs_tree_inspect_label(BSTreePos pos)

// Check if the node at the position has a left child. bool bs_tree_has_left_child(BSTreePos pos)

// Check if the node at the position has a right child. bool bs_tree_has_right_child(BSTreePos pos)

// Get the position of the root. BSTreePos bs_tree_root(BSTree *tree){ BSTreePos *ptr = &tree; return *ptr; }

// Get the position of the left child to the node with position pos. BSTreePos bs_tree_left_child(BSTreePos pos)

// Get the position of the right child to the node with position pos. BSTreePos bs_tree_right_child(BSTreePos pos)

// Deallocate the binary search tree. void bs_tree_destroy(BSTree *tree)

// Declarations of functions. void print_array(int n, int a[]); void swap(int *a, int *b); void insert_value(int value, BSTreePos first_pos); BSTreePos search_value(int value, BSTreePos first_pos);

int main(void) { // Create an array with the values 1, 2, ..., 10 and print out the content. int n = 10; int arr[n];

srand(time(0));

for (int i = 0 ; i < n ; i++) { arr[i] = i + 1; }

print_array(n, arr);

// Shuffle the values in the array and print out the content. for (int i = n - 1 ; i > 0 ; i--) { int j = rand() % i; swap(&arr[j], &arr[i]); }

print_array(n, arr);

// Create a binary search tree and insert the values in the array. BSTree *tree = bs_tree_make(arr[0]); for (int i = 1 ; i < n ; i++) { BSTreePos pos = bs_tree_root(tree); insert_value(arr[i], pos); }

// Search the binary search tree for each of the values in the array and // print out the result of the search. for (int i = 0 ; i < n ; i++) { BSTreePos pos = bs_tree_root(tree); if (search_value(arr[i], pos) == NULL) { printf("Value %d not found ", arr[i]); } else { printf("Value %d found ", arr[i]); } }

// Search the binary search tree for a value that is not in the array and // print out the result of the search. BSTreePos pos = bs_tree_root(tree); int x = 99; if (search_value(x, pos) == NULL) { printf("Value %d not found ", x); } else { printf("Value %d found ", x); }

// Destroy the binary search tree. bs_tree_destroy(tree);

return 0; }

// Print the array. void print_array(int n, int a[]) { printf("Array: "); for (int i = 0 ; i < n ; i++) { printf("%d ", a[i]); } printf(" "); }

// Swap the values. void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; }

// Insert a value in the tree. void insert_value(int value, BSTreePos pos) { if (pos == NULL) return bs_tree_make(value); if (value < pos->value) { pos->left_child = insert_node(pos->left_child, value); } else if (value > pos->value) { pos->right_child = insert_node(pos->right_child, value); }

}

// Search for a value in the tree. BSTreePos search_value(int value, BSTreePos pos) { }