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): // Tree definition for problem 3 type BST = | Empty | TreeNode of int * BST * BST i. 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.
In F# 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):
// Tree definition for problem 3
type BST =
| Empty
| TreeNode of int * BST * BST
i. 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.
ii. contains value tree
Returns true if the value is in the tree or false if it is not.
iii. 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.
iv. 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).
NOTE:
- Do not use "mutable" variables. Example any use of the mutable keyword.
- Functions should have no side effects. This includes:
- no output (other than the function's return value) - e.g., no use of printfn or file output
- no input (other than the function's arguments) - e.g., no user input or file input
- no use of external state - e.g., global or static variables
- In particular, you may not use F# system functions or methods (such as map or max).
- You may define and use additional functions (e.g., helper functions) if your feel it is appropriate.
- Think about what appropriate test cases for each of the functions you implement should be (including any "helper functions" that you choose to create). Be sure to think about all the edge cases and exceptions to normal behavior (e.g., what if the list input is an empty list?). Do not assume any input is invalid unless the assignment description below explicitly says you may, or it would violate F#'s type checking.
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)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 6 images
