PROGRAM 6 Binary Search Trees Solution

__In this program, you will learn to__:




* Work with a Binary Search Tree




:warning: *For all Data Structures, you may (and probably should) add additional functions, methods, and attributes, but what follows is the required minimum interface*




Part A: BST

Create a link based Binary Search tree composed of a Node and Tree struct. You should have a header file, bst.h, with the following:




* Node struct containing left, right, and parent pointers, in addition to holding an Data struct value.

* Tree struct containing a pointer to the root of the tree.

* A function declaration for a function that allocates a tree, and initializes the root to NULL;

* A function declaration for a function that takes a Data struct as a parameter, allocates a node, and initializes the left, right, parent fields to NULL.

* You should also have a source file, bst.c, that implements the two declared functions:

* Tree * newTree();

* Node * newNode(Data d, Node * parent);

Test your functions and structure to ensure everything is initialized correctly by creating a Tree and adding a root to it.




Below is the expected interface for your structs:




* Data struct

* `value (int)`




* Node struct

* `data (Data)`

* `left (Node *)`

* `right (Node *)`

* `parent (Node *)`




* Tree struct

* `root (Node *)`

* `Data * (*insert)(Tree *, Data);`

* `Data * (*search)(Tree * bst, Data value);`

* `void (*sort)(Tree *, Data *);`

* `int (*compare)(Tree *t, Tree * copy);`

* `Tree * (*clone)(Tree *t);`

* `void (*delete)(Tree * bst);`

* `void (*removeData)(Tree * bst, Data value);`




Your constructors should have the following interfaces:

* `Node * newNode(Data d, Node * parent);`

* `Tree * newTree();`




Part B: BST Operations

Implement the following operations in your BST.c file.

INSERT:

`Data * (*insert)(Tree * bst, Data value)` - Inserts into the tree.




:bulb: Helpful Hints

* Return a pointer to the Data value inserted into the tree

* Make sure you check for the special case of an empty tree [if(bst-root == NULL)],

* After checking for the root, use a separate helper function to insert a value into the tree, `Data * insertNode(Node * node, Data value)`, that you can use for the recursive call

* If the value is already in the tree, return NULL




SEARCH:

`Data * (*search)(Tree * bst, Data value)` - Searches for a value in the tree. Return a pointer to the Data object if found.




:bulb: Helpful hints:

* Make sure you check for the special case of an empty tree [if`(bst-root == NULL)`],

* After checking for the root, use a separate helper function to search the tree, Node * searchNode(Node * node, Data value), that you can use for the recursive call




REMOVE:

`void (*removeData)(Tree * bst, Data value)` - Removes a value from the tree




:bulb: Helpful hints:

* Use your (hopefully) working search auxiliary function to find the node you need to delete

* Your auxiliary search function can return a node pointer, and you primary search function returns the data from that pointer.

* You will have 3 cases requiring 3 separate functions:

* remove a leaf node : `void removeLeaf(Tree * bst, Node * d_node)`

* remove a node with 1 branch: `void shortCircuit(Tree * bst, Node * d_node)`

* remove a node with 2 branches: `void promotion(Tree * bst, Node * d_node)`

* You will need to use your `removeLeaf()` and `shortCircuit()` functions in your promotion function, so make sure they are working before starting on the promotion function.







You will also need to implement the following:

* `Tree * (*clone)(Tree*)`: Takes a tree and uses preorder traversal algorithm to return a clone of the tree

* `int (*compare)(Tree*, Tree*)`: Takes a tree and uses preorder traversal algorithm to determine if the trees are equal

* `void (*sort)(Tree *, Data *)`: Takes a tree and a data array buffer as parameters, and fills the buffer with the tree data in sorted order using the inorder traversal algorithm.

* `void (*delete)(Tree * bst)`: Add a post-order deleteTree() function that deletes all nodes and the tree

* :bulb: post order only deletes leafs, so you need only call deleteLeaf()

* :bulb: Each of the above functions is easier to implement if you use an auxiliary recursive function




Part C: Submission




Required file naming and organization:

* program6.c //Driver Code

* bst.c/h

* makefile

* You must have the following labels in your makefile:

* all - to compile all your code to an executable called ‘program4’ (no extension). Do not run.

* run - to compile if necessary and run

* memcheck - to compile only if necessary and run with valgrind

* clean - to remove all executables and object files




:no_entry: Every program will have a required submission guidelines. Please read submission requirements carefully. Any deviations from specifications will result in point deductions or incomplete grades.




README




* KNOWN BUGS AND INCOMPLETE PARTS

* REFERENCES

* MISCELLANEOUS COMMENTS




Before your final submission, edit the content for each of these sections in this README for your program. You do not have to use markdown, but you can find out more about markdown [here](https://guides.github.com/features/mastering-markdown/) if you would like to.




Git




Below is a reminder of the commands you need to use to submit your program.




:warning: You have created several files and even a folder for this program. Be sure you add them to the repo. If you forget to add the files to the repo, your assignment will be considered late or not accepted at all.




```shell

git status

git add mylib.h

git commit -a -m "commit message"

git push

```




To find your most recent commit hash, use the following command:




```shell

git rev-parse HEAD

```




To complete your submission, you must copy and paste this number into mycourses. Go to MyCourses, select cs580u, and **Assignment Hash Submission**.




:warning: You __MUST__ submit the commit hash on mycourses before the deadline to be considered on time **even if your program is completely working before the deadline**. :warning: