Need help with ocaml binary search trees!

In this problem, we will consider using a binary search tree to represent a database. We will separate out one item of the tuples we want to represent as the key based on which we will organize the tree, and the remaining items will form the data corresponding to the key. The key is also often called the index to the data. For example, in the employee database, the key or index might be the name of the employee and the data may be a tuple consisting of the salary and the phone number. The information in the data base would then be organized into a tree structure such as the following

 (key1,data1) / \ / \ (key2,data2) (key3,data3) / \ / \ / \ / \ (key4,data4) Empty Empty (key5,data5) . . . 

In other words, the internal nodes of such trees hold the key and the data items, each internal node has a left and a right subtree and the leaves are empty trees. Of course, since this is a binary search tree, the organization is such that the keys in the left subtree at any point are smaller than the key at the node and the keys in the right subtree are larger than the key at the node; note that this property holds recursively as described.

1. Provide a type declaration that identifies a type constructor called btree that takes a pair of arguments corresponding to the type of the key and the type of the data and associated value constructors that can be used to represent trees of the form shown above. After you have provided this declaration, we should be able to write down OCaml expressions of type (ty1,ty2) btree, for suitable types ty1 and ty2, that represent trees of the kind we are interested in.

   Note: The OCaml type system is not strong enough to capture the ordering property for search trees, so don't spend time trying to do this. Instead, this ordering property will be an invariant of the trees we construct and manipulate through the functions we write. In other words, we should stipulate the property as a requirement for the trees input to our functions and we should ensure that the definitions we write are such that any output trees maintain the property.

2. Provide a let binding that binds the identifier inittree to the encoding of the empty tree.
3. Write down two expressions in OCaml that uses the type declarations you have provided to represent two non trivial binary search trees over different kinds of keys and data. More specifically, you should have code of the form

    let tree1 = ... let tree2 = ... 

   where ... is the expression representing a relevant binary search tree. In the first tree, use an integer as the key and a string as the data. In the second tree use a string (representing a person name) as the key and a string and a real (representing a phone number and a salary) as the data. Note that we will check if the expressions you provide are of the right type by looking at their types and by determining if they satisfy the binary search tree requirement using the standard ordering on integers and strings.
4. Define a function of the following name and type

    find : ('a, 'b) btree -> 'a -> 'b option 

   that takes a binary search tree and a key as input and that returns the data value stored in the tree corresponding to the key. Assume that there is exactly one entry per key in the tree. The return type has the option form in case the tree does not contain an entry corresponding to the given key. In defining this function you should obviously assume the invariant associated with binary search trees.
5. Define a function of the following name and type

    insert : ('a, 'b) btree -> 'a -> 'b -> ('a, 'b) btree 

   that takes a binary search tree, a key and a data item and returns a new binary search tree that corresponds to the old tree with the given key and data item pair inserted into it. In case your experience with programming in languages such as Java or C is confusing you, note that we do not modify the old tree in OCaml but we can reuse parts of it in constructing the new tree. You should assume that the input tree satisfies the ordering invariant on binary search trees and your function is expected to preserve this invariant. One other question that often comes up: what should we do if the key already appears in the tree? We resolve the question in the following way for this problem: the new tree should not have the old key and data association, it should have only the new one.

   One important question: what ordering relation to use on the key type? In this assignment, assume that the usual, overloaded ordering relations < and > and also the equality relation = will work on this type, i.e., you can use them directly in your code.

6. Define a function of the following name and type

    keylist : ('a, 'b) btree -> ('a list) 

   that will traverse the tree and produce a list of the keys in it in the following order: first the keys in the left subtree will be listed, then the key at a node and then the keys in the right subtree. This kind of traversal is called an in-order traversal and it has the result of producing an ordered listing of the keys.
7. Define a function of the following name and type

    delete : ('a, 'b) btree -> 'a -> ('a, 'b) btree 

   that takes a binary search tree and a key and returns a new binary search tree that corresponds to the old tree with a possible entry in it corresponding to the given key removed. Remember, you have to maintain the invariant for binary search trees in the process.

   Hint: First write a function that takes a non-empty tree and produces a new tree from it that does not contain what was at the root; in my code, I called this function delete_root. Then organize the delete function so that it locates the node to be removed and uses delete_root to do this.