In this project we will build a binary search tree of strings. The main program will consist of a menu of choices for the user:

1) Add an item
2) Delete an item
3) Search for an item
4) Print the list inorder
5) Print the tree (in tree format)
6) (Optional) Balance the tree
7) Exit

To delete a node there are three cases:

a) the node is a leaf:

 1) set a temp pointer to the node_to_be_deleted
 2) set the parent's pointer to that node to null
 3) deallocate the node

b) the node has one child:

 1) set a temp pointer to the node_to_be_deleted
 2) set the parent's pointer to the node_to_be_deleted's child pointer
 3) deallocate the node

c) the node has two children:

 1) Set a temp pointer to the node_to_be_deleted.
 2) Set a pointer to the parent of the largest node in the left subtree of the node_to_be_deleted.
 3) Set a pointer to the largest node in the left subtree of the node_to_be_deleted.
 4) Copy the data from the largest node in the left subtree to the node_to_be_deleted.
 5) Set the parent's right child pointer to the largest_node_in_the_left_subtree's left child. (It may be null, that's okay)
 6) Deallocate the largest node in the left subtree.

To balance the tree:

a) Traverse the tree inorder, putting the data into an array, keeping track of the size of the array.
b) Using a binary search technique, find the middle item in the array, and add it to an empty tree.
c) Recursively find the middle of both the left and right sub-arrays, and make those the right and left children respectively.
d) Recursion stops when the left or right sub-array is of size 0, or the current sub-array is of size 1.
e) Be sure to set leaf node’s child pointers to null

To print the tree in tree format:

Follow the directions in exercise 20.25, page 989 of your textbook.