Write the following binary search tree functions for a binary search tree of integers. (This will essentially be a tree set, i.e., a set data structure implemented using a tree.) Use the following type definition for a BST (copy this into your solution):

1. insert value tree
   • Inserts the value into the tree and returns the resulting tree. The resulting tree does NOT need to be balanced. If the value already exists in the tree, return the tree without inserting the value.
2. contains value tree
   • Returns true if the value is in the tree or false if it is not.
3. count func tree
   • The parameter func is a Boolean function that takes a single parameter and returns true or false. The function tests the value of each node with func and returns the number of nodes that evaluate to true.
4. evenCount tree
   • Returns the number of nodes that contain even integers.
   • REQUIREMENT: This function may not call any other function by name, except for the count function. However, you may use lambda functions (which do not have a name).

Examples in F# Interactive:

> let bt1 = insert 10 Empty;; val bt1 : BST = TreeNode (10,Empty,Empty)

> let bt2 = insert 5 bt1;; val bt2 : BST = TreeNode (10,TreeNode (5,Empty,Empty),Empty)

> let bt3 = insert 3 bt2;; val bt3 : BST = TreeNode (10,TreeNode (5,TreeNode (3,Empty,Empty),Empty),Empty)

> let bt4 = insert 17 bt3;; val bt4 : BST = TreeNode (10,TreeNode (5,TreeNode (3,Empty,Empty),Empty),TreeNode (17,Empty,Empty))

> let bt5 = insert 12 bt4;; val bt5 : BST = TreeNode (10,TreeNode (5,TreeNode (3,Empty,Empty),Empty), TreeNode (17,TreeNode (12,Empty,Empty),Empty))

> contains 17 bt5;; val it : bool = true > contains 4 bt5;; val it : bool = false > evenCount bt5;; val it : int = 2 > let gtTen x = x > 10 > count gtTen bt5;; val it : int = 2