Use Ocaml programing:

Base Code:

(** Trees **)

type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree ;;

let rec tree_fold (t: 'a tree) (u: 'b) (f: 'a -> 'b -> 'b -> 'b) = match t with | Leaf -> u | Node (v, l, r) -> f v (tree_fold l u f) (tree_fold r u f)

(*>* Problem 2.1 *>*) let tree_map (t: 'a tree) (f: 'a -> 'b) : 'b tree = raise ImplementMe

(*>* Problem 2.2 *>*) let inorder (t: 'a tree) : 'a list = raise ImplementMe

(*>* Problem 2.3 *>*) let preorder (t: 'a tree) : 'a list = raise ImplementMe

2 Trees For this section, put your answers in trees.ml. Higher-order functions aren't just for lists! Recall the algebraic data type of binary trees from lecture: type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree In this section, you'll implement and use higher-order functions over trees. As an example, we implemented the function tree_fold : 'a tree -> 'b-> ('a -> ' -> ' -> 'b) that folds over trees like List.fold_right folds over lists. For example, tree_fold (Node (v1, Node (v2, Leaf, Leaf), Leaf)) u f is f v1 (f v2 u u) u. Note that our implementation isn't tail-recursive. The Cornell book (linked from the course website) gives a tail-recursive version. Task 2.1 (Programming, 5 points). Implement the function tree_map : 'a tree -> ('a -> 'b) -> 'b tree that returns a tree with the same structure as the original tree, but with the given function applied to every node. Use tree_fold. Do not use recursion. There are various ways of traversing a tree to flatten it. Consider the tree below. 3 4 5 An in-order traversal goes down the left subtree of a node first, then visits the node itself, then the right subtree. A in-order traversal of the above tree would visit nodes in the order 4, 2, 5, 1, 3. You can think of this as basically visiting the nodes left-to-right as they're drawn on the page. A pre-order traversal visits the node itself, then the left subtree, then the right subtree. A pre-order traversal of the above tree visits the nodes in the order 1, 2, 4, 5, 3. Task 2.2 (Programming, 5 points). Implement the function inorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an in-order traversal. (So, inorder applied to the above tree would give [4;2;5;1;3].) Use tree_fold. Do not use recursion. Task 2.3 (Programming, 5 points). Implement the function preorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an pre-order traversal. (So, preorder applied to the above tree would give (1;2;4;5;3].) Use tree_fold. Do not use recursion. 2 Trees For this section, put your answers in trees.ml. Higher-order functions aren't just for lists! Recall the algebraic data type of binary trees from lecture: type 'a tree = Leaf | Node of 'a * 'a tree * 'a tree In this section, you'll implement and use higher-order functions over trees. As an example, we implemented the function tree_fold : 'a tree -> 'b-> ('a -> ' -> ' -> 'b) that folds over trees like List.fold_right folds over lists. For example, tree_fold (Node (v1, Node (v2, Leaf, Leaf), Leaf)) u f is f v1 (f v2 u u) u. Note that our implementation isn't tail-recursive. The Cornell book (linked from the course website) gives a tail-recursive version. Task 2.1 (Programming, 5 points). Implement the function tree_map : 'a tree -> ('a -> 'b) -> 'b tree that returns a tree with the same structure as the original tree, but with the given function applied to every node. Use tree_fold. Do not use recursion. There are various ways of traversing a tree to flatten it. Consider the tree below. 3 4 5 An in-order traversal goes down the left subtree of a node first, then visits the node itself, then the right subtree. A in-order traversal of the above tree would visit nodes in the order 4, 2, 5, 1, 3. You can think of this as basically visiting the nodes left-to-right as they're drawn on the page. A pre-order traversal visits the node itself, then the left subtree, then the right subtree. A pre-order traversal of the above tree visits the nodes in the order 1, 2, 4, 5, 3. Task 2.2 (Programming, 5 points). Implement the function inorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an in-order traversal. (So, inorder applied to the above tree would give [4;2;5;1;3].) Use tree_fold. Do not use recursion. Task 2.3 (Programming, 5 points). Implement the function preorder : 'a tree -> 'a list that lists the nodes of a tree in the order given by an pre-order traversal. (So, preorder applied to the above tree would give (1;2;4;5;3].) Use tree_fold. Do not use recursion