Use Ocaml Language.
Task 2 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.
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.
Task3 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.
Task4 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.
The base code:
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 *>*)
let tree_map (t: ‘a tree) (f: ‘a -> ‘b) : ‘b tree =
raise ImplementMe
(*>* Problem 3*>*)
let inorder (t: ‘a tree) : ‘a list =
raise ImplementMe
(*>* Problem 4 *>*)
let preorder (t: ‘a tree) : ‘a list =
raise ImplementMe
