Revised 2016 Nov 14.¹

There are three parts: Binary Trees, General Trees, Binary Search Trees. All require writing and testing Haskell code. Import the following provided modules as needed:

• BinaryTree.hs
• GeneralTree.hs
• BinarySearchTree.hs
• TreeSet.hs

For each of the three parts, you should turn in one Haskell source file and one test I/O file. You do not need to turn in the provided code.

Part A: Binary Trees

1. (3 points) Here is the inorder traversal function. Given a binary tree, this returns a list of the elements in order.

   inorder :: BinaryTree a -> [a]
   inorder Empty = []
   inorder (Node root left right) = 
     inorder left ++ [root] ++ inorder right

   The ++ operator concatenates lists:

   Prelude> [1, 2, 3] ++ [4, 5]
   [1,2,3,4,5]

   Similarly, define the postorder traversal function.

2. (5 points) Define a function which, given a binary tree, returns a list of the leaves of the tree. The type declaration for this function is

   leaves :: BinaryTree a -> [a]

3. (2 points) Test your functions using the binary tree t1 defined in BinaryTree.hs:

   

4. Turn in: source file and test I/O.

Part B: General Trees

1. (5 points) Define a function which, given a general tree, returns a list of its leaves. The type declaration for this is

   leaves :: Tree a -> [a]

2. (5 points) Define a function, level, which given a tree and an integer n ≥ 0, returns a list of the nodes at level n. The root’s level is 0. This function should return the empty list, [], if the level given is greater than the height of the tree.

   The type declaration for this is

   level :: Int -> Tree a -> [a]

3. (2 points) Test your functions using the general tree t1 defined in GeneralTree.hs:

   

4. Turn in: source file and test I/O.

Hints

You’ll find concatMap useful for operating on the subtrees. This function combines concat, which “flattens” a list of lists, and map, which applies a function to each element in a list:

Prelude> concat [[1,2,3], [], [4,5], [6,7,8]]
[1,2,3,4,5,6,7,8]

Prelude> map (+ 1) [1..6]
[2,3,4,5,6,7]
Prelude> let f n = [1..n]
Prelude> f 5
[1,2,3,4,5]
Prelude> f 0
[]
Prelude> map f [2, 3, -1, 5]
[[1,2],[1,2,3],[],[1,2,3,4,5]]

Prelude> concat (map f [2, 3, -1, 5])
[1,2,1,2,3,1,2,3,4,5]
Prelude> concatMap f [2, 3, -1, 5]
[1,2,1,2,3,1,2,3,4,5]

In Haskell, we can partially apply a function by supplyying it with some but not all of its arguments. The result of partial application is always a function.

For example, the level function takes two arguments: an Int and a Tree. If we partially apply it by supplying the Int argument, we get a function which then needs only a Tree argument: level 5 has the type Tree a -> [a], so it can be applied to a Tree and will return a list. Functions such as level 5 or in general level n, level (n - 1), etc., can be given as arguments to map, concatMap, and similar functions. This can be very useful.

Part C: Binary Search Trees

1. (5 points) Here is a function with two arguments: a value x, and a binary search tree t. The function returns a binary search tree containing all the elements in t which are ≤ x.

   getLe :: (Ord a) => a -> BinaryTree a -> BinaryTree a
   getLe _ Empty = Empty
   getLe x (Node root left right) =
     if root <= x
     then Node root left (getLe x right)
     else getLe x left

   Similarly, define a function getGE which returns a binary search tree containing all the elements in t which are ≥ x.

2. (3 points) Define a function with three arguments: a lower bound a, an upper bound b, and a binary search tree t, The function returns a binary search tree containing all the elements x in t such that a ≤ x ≤ b. The type of this function is

   getRange :: (Ord a) => BinaryTree a -> a -> a -> BinaryTree a

   Defining getRange is easy if you use the functions getLE and getGE from the previous problem.

3. (2 points) Testing: print the inorder traversal of the trees resulting from the following searches:

   1. x in t3, x ≤ 75
   2. x in t3, x ≤ 130
   3. x in t3, x ≥ 150
   4. x in t3, x ≥ 65
   5. x in t4, “jest” ≤ x ≤ “rat”
   6. x in t4, “coot” ≤ x ≤ “goose”
   7. x in t4, “man” ≤ x ≤ “woman”

   using the two test trees below, which are defined in BinaryTree.hs:

   Binary search tree t3	Binary search tree t4

4. Turn in: source code and test I/O.

What to Turn in

Three source files and three test sessions (see Parts 1, 2, 3 for details).

Do not turn in the provided code.

Scoring Summary

• Part A: 10 points
• Part B: 12 points
• Part C: 10 points
• Code style: 3 points

Total: 35 points