• Write a C program that works with binary search trees (BSTs).

Requirements

As starter code for this assignment, use the C code contained in as7_starter_code.zip file found on Avenue to Learn accompanying this assignment.

This starter code contains the same binary search tree type used in lectures and labs, and the same set of functions for working with binary search trees that we created together in lecture and lab. The starter code also contains the following function declarations:

// HINT: This function was used as a helper function for array_of_sorted_keys // in the instructors solution:

// void build_array(bstNode *node, int *array, int *current_index); int *array_of_sorted_keys(bstNode *node);

// HINT: This function was used as a helper function for

// balanced_tree_from_sorted_array in the instructors solution:

// bstNode *construct_tree(int *array, int min, int max);

bstNode *balanced_tree_from_sorted_array(int *sorted_array, int length);

bstNode *balanced_tree_copy(bstNode *tree);

At a minimum you will need to implement the array_of_sorted_keys,

balanced_tree_from_sorted_array, and balanced_tree_copy functions. Two function declarations have been commented out in the starter code, but they were used by the instructor to create their solution to the problems, and so you can implement these as well if you find them helpful (I would recommend implementing them).

The array_of_sorted_keys function must accept as an argument the head node of a BST. It needs to return a pointer to a dynamically allocated array that contains the keys of the BST sorted in ascending order. In order to do this, youll need to dynamically allocate an array large enough to hold all of the keys. The num_nodes function can help you with this. In the week 9 lab youll learn that you can print out the keys of a BST in an ascending sorted order if you do an in-order traversal of the tree. In this case, instead of printing the nodes, youll need to store them in the dynamically allocated array that youve created.

In the instructors solution, they used a helper function void build_array(bstNode *node, int *array, int *current_index) which performed an in-order traversal of the BST, storing the results into array, and using current_index to keep track of the index to place the next element visited into the array. You dont have to solve the problem exactly this way, but this way is recommended, and whatever you do, do not use a global variable to manage this.

The balanced_tree_from_sorted_array function needs to accept as arguments an array of ints stored in ascending sorted order, and the length of that array. It needs to return a pointer to a newly created balanced binary search tree that contains as keys all of the elements in the array (i.e. you are converting the array contents to a balanced binary search tree). A balanced binary search tree has the minimum height necessary to contains all of the keys. If you wanted to create a balanced tree from a sorted array, then the best node for the root node would be the middle element of the array, given that half the array elements will be less than this element and half the array elements will be greater than this element. If the array contains an even number of elements either of the two middle elements will work. If you recursively applied this logic to each remaining left and right subsection of the array to build the left and right subtrees of this node, you could build a balanced binary search tree. So a function could work like this:

1. Is there still a middle to be found? If not, return NULL.
2. Get the middle of the array, create a new node with this value as the key.
3. Take the left half of the array, call the function recursively and set the left child of the node to the result.
4. Take the right half of the array, call the function recursively and set the right child of the node to the result.
5. Return the node.

In order to do this, the instructors solution used a helper function bstNode *construct_tree(int *array, int min, int max) where min is the beginning index of the segment of the array being converted, and the max is the ending index of the segment of the array being converted. By recursively calling construct_tree with min and max values that reflect the portion of the array being converted for a given subtree, we can follow the above algorithm. We detect that there is no longer a middle that can be found when the function is called with a min > max. You do not need to solve the problem exactly this way, but this is the recommended approach.

The balanced_tree_copy function should accept as input a binary search tree that is potentially unbalanced. It should return a copy to a new balanced binary search tree on the heap which contains the same keys. In order to do this, you can call the array_of_sorted_keys function to obtain an array containing the keys of the binary search tree in ascending sorted order. Then you can call balanced_tree_from_sorted_array to obtain a balanced binary search tree from these results. Dont forget to free the array you created as there is no need for it after the function is done!

Test Code

The main function contains test code to test the 3 functions. You may want to comment out this code by surrounding it with /* */ multiline comments so that you can work on your functions, as the code assumes that all of the functions have been implemented. You can use this code to help verify that your functions are working correctly.

The expected test code results are provided after the mark breakdown, and as a plaintext file on Avenue to Learn accompanying the assignment.