## Description

In this assignment, you will implement a binary tree data structure in two languages: one in

Haskell, and one in an imperative language (C, C++, Java, or C#).

The portion of your solution in Haskell should be defined within a module named Tree, and

you should submit the file Tree.hs (or Tree.lhs). File names are case sensitive. The

portion of your solution in C/Java should be defined within a file named Tree.* or tree.*

where * is the appropriate extension. Verbal responses to non-programming questions should

be in the form of comments in your code.

Note: The solution to each part of the Haskell problems is meant to be extremely short

(one to four lines). You may (and should) use functions from earlier problems to solve parts

of later problems. Unless otherwise specified, your solutions may utilize functions from the

standard prelude as well as material from the lecture notes and textbook.

## Problem 1. (20 pts)

(a) Define a polymorphic data type called Tree a that has two constructors: Leaf ::

Tree a and Node :: a -> Tree a -> Tree a -> Tree a. Trees of this type will

contain a single piece of data of type a at each node, and no data at their leaves.

(b) Modify your data type definition so that the show and (==) functions are both defined

for it.1

(c) Define a function mapT :: (a -> b) -> Tree a -> Tree b that operates on trees

the same way that map operates on lists. In other words, mapT should take a function

and apply it to every data item of type a within a tree of type Tree a.

(d) Define a function foldT :: (a -> b -> b -> b) -> b -> Tree a -> b that operates on trees the same way that foldr operates on lists. In other words, the base item

of type b should replace the leaf constructor in the tree, and the function of type a ->

b -> b -> b should replace the node constructor in the tree.

1Hint: This should be done as part of the original data expression by adding a deriving clause, consult

[HCFP, Ch. 14, 16].

1

## Problem 2. (20 pts)

(a) Define a function leafCount :: Tree a -> Integer that returns an integer representing the total number of leaves in a tree. To get full credit, you must use foldT and

may define at most one helper function.

(b) Define a function nodeCount :: Tree a -> Integer that returns an integer representing the total number of non-leaf nodes in a tree. To get full credit, you must use

foldT and may define at most one helper function.

(c) Define a function height :: Tree a -> Integer that returns an integer representing

the height of the tree. Trees consisting of only a leaf have height 0. To get full credit,

you must use foldT and may define at most one helper function.

## Problem 3. (30 pts)

(a) A tree is perfect if all the leaves of the tree are at the same depth. Define a function

perfect :: Tree a -> Bool that returns True if the tree supplied is perfect and

False otherwise. You may use any approach to implement this function.

(b) A tree is a degenerate if all the nodes are arranged in a single path. Equivalently, a tree

is degenerate if all nodes have at least one leaf child. Define a function degenerate ::

Tree a -> Bool that returns True if and only if the tree supplied is degenerate.2

(c) Define a function list :: Tree a -> Maybe [a]. If the supplied tree is degenerate

the function should return Just l, where l corresponds to a list constructed by replacing the Node constructors with (:) constructors and the Leaf constructors have been

replaced with the [] constructor where appropriate. If the supplied tree is not degenerate, the function should return Nothing. You are encouraged to use degenerate and

foldT to implement this function.3

## Problem 4. (30 pts)

(a) Implement in an imperative language a data structure definition similar to Tree a.

(b) Add functions or members to the data structure definition corresponding to the functions (==), leafCount, nodeCount, height, perfect, degenerate, and list (the last

function can return an array or other list-like data structure instance if possible, and

null or something equivalent otherwise). You may use any approach to implement

these functions.

(c) Identify two advantages of higher-order functions (such as foldT) within the context

of processing tree data structures.

2Hint: You do not need to make your function recursive if you use functions you have already defined.

How many leaves does a degenerate tree have? How many nodes?

3Hint: Do not make your use of foldT more complicated than necessary. Do you need to check that the

tree is degenerate more than once? Use your nodeCount implementation as a guide.

2

Problem 5. (

∗15 extra credit pts)

(a) In your Tree module, define a new data type called Color that has four constructors:

Red::Color, Green::Color, Blue::Color, and Yellow::Color.

(b) Define a value infColorTree :: Tree Color, an infinite tree in which every node

has a color, and the three neighbors of that node (the parent and its two children) have

three distinct colors which are different from the color of the node. (That is, for every

node 푣, the two children of that node must have different colors from each other as well

as from 푣, and the parent of 푣 must not share a color with either of the two children of

푣, nor with 푣 itself).

3