This question should be answered with OCaml. All functions must be implemented with the Continuation Passing Style. Trees, especially binary trees, are frequently used data structures. Let’s assume a binary tree is represented using the following definition. type ’a tree = Empty | Tree of ’a tree * ’a * ’a tree Each node is in itself a tree and carries an item of type 'a. Additionally, each node has a left and right subtree. Leaf nodes are marked with an Empty left and right subtree. This definition is very similar to that of list, with the difference being that each Node (item) has two sub-Nodes in a tree, compared to one in case of a list. Oftentimes we want to traverse an entire tree in a certain order. One common way of traversing a tree is postorder traversal. In postorder traversal, we traverse the left subtree first, then traverse the right subtree, then visit the node. Our job is to create a function that returns a list of the values of the tree visited in postorder traversal. This function should be implemented with the Continuation Passing Style. Our function would have the following signature: traverse : 'a tree -> 'a list Example 1: For the tree in the image above, traverse should return the list [2; 5; 11; 6; 7; 5; 9; 9; 1]. Example 2: Input: Tree (Tree (Empty, 2, Empty), 1, Tree (Empty, 3, Empty)) Output: [2; 3; 1] Example 3: Input: Tree (Tree (Tree (Empty, 4, Empty), 2, Tree (Empty, 5, Empty)), 1, Tree (Empty, 3, Empty)) Output: [4; 5; 2; 3; 1] Question: 1. Write some test cases for testing the tree traversal function. let traverse_tests : (int tree * int list) list = [] 2. Implement a CPS style postorder traversal function. let traverse (tree : 'a tree) : 'a list = let rec helper (tree : 'a tree) (sc: (unit -> 'a list)) = match tree with | Empty -> sc () | Tree (left, value, right) -> helper left (fun () -> helper right (fun () -> sc (value :: (helper left (fun () -> helper right (fun () -> []))) ))) in helper tree (fun x -> x) Hint: You may want to create a recursive helper function with the following type signature: helper : 'a tree -> (unit -> 'a list) -> 'a list
This question should be answered with OCaml. All functions must be implemented with the Continuation Passing Style.
Trees, especially binary trees, are frequently used data structures. Let’s assume a binary tree is represented using the following definition.
type ’a tree = Empty | Tree of ’a tree * ’a * ’a tree
Each node is in itself a tree and carries an item of type 'a. Additionally, each node has a left and right subtree. Leaf nodes are marked with an Empty left and right subtree. This definition is very similar to that of list, with the difference being that each Node (item) has two sub-Nodes in a tree, compared to one in case of a list.
Oftentimes we want to traverse an entire tree in a certain order. One common way of traversing a tree is postorder traversal.
In postorder traversal, we traverse the left subtree first, then traverse the right subtree, then visit the node.
Our job is to create a function that returns a list of the values of the tree visited in postorder traversal. This function should be implemented with the Continuation Passing Style. Our function would have the following signature:
traverse : 'a tree -> 'a list
Example 1: For the tree in the image above, traverse should return the list [2; 5; 11; 6; 7; 5; 9; 9; 1].
Example 2:
- Input: Tree (Tree (Empty, 2, Empty), 1, Tree (Empty, 3, Empty))
- Output: [2; 3; 1]
Example 3:
- Input: Tree (Tree (Tree (Empty, 4, Empty), 2, Tree (Empty, 5, Empty)), 1, Tree (Empty, 3, Empty))
- Output: [4; 5; 2; 3; 1]
Question:
1. Write some test cases for testing the tree traversal function.
let traverse_tests : (int tree * int list) list = []
2. Implement a CPS style postorder traversal function.
let traverse (tree : 'a tree) : 'a list =
let rec helper (tree : 'a tree) (sc: (unit -> 'a list)) =
match tree with
| Empty -> sc ()
| Tree (left, value, right) ->
helper left (fun () ->
helper right (fun () ->
sc (value :: (helper left (fun () -> helper right (fun () -> []))) )))
in
helper tree (fun x -> x)
Hint: You may want to create a recursive helper function with the following type signature:
helper : 'a tree -> (unit -> 'a list) -> 'a list
Step by step
Solved in 3 steps
