For this assignment, you will implement a binary search tree using memory allocation in C. There are four methods to write: bst_add, bst_contains, and bst_destroy.
Pseudocode and detailed descriptions have been defined for each method inside of the javadocs in binary search tree.c.
1.1 Binary Search Trees
A binary search tree is a node-based data structure with the following properties:
• each node has a maximum of two children.
• the left subtree of a node contains only nodes with values less than the value of the original node.
• the right subtree of a node contains only nodes with values greater than the value of the original node.
• the left and right subtrees must also be binary search trees.
In the example bst, you will notice that all children to the left of a parent node are of smaller value than the parent itself, and the children to the right of a parent node are of greater value than the parent itself. The basic process for memory allocation for a bst is not unlike the process used with linked lists, so feel free to reference Homework 8.
2 Instructions
You will be editing ONLY binary search tree.c. We have defined the bst node struct in the binary search tree.h file. Instructions for each method have been provided in the javadocs for each method in binary search tree.c.
All #include directives have been included for you. Do not add any more includes. Doing so will result in point deductions that the tester will not reflect.
