Week 10: Exercises

Solve the following problems in Haskell.

1. Integers with Infinity

1. Write a data type IntX that represents an integer, positive infinity, or negative infinity. Write functions less and greater on this type.

2. Generalize IntX to work with any appropriate base type, not just integers.

2. Valid Search Tree

Write a function isSearchTree that determines whether a binary tree is a valid binary search tree. Assume that duplicate values are not allowed in the tree.

3. Tree Values

Write a function that takes a binary search tree and returns a list of all its values in order. Your function should run in time O(N), where N is the number of nodes in the tree.