Trees

Consider the following Binary Tree type

data Tree a = Leaf | Node (Tree a) a (Tree a)

1 inClass

Write the function elemTree that tests if an element x occurs in a binary search tree of type Tree a.

2 atHome

Write functions that return all values of type a in a tree of type Tree a in depth-first (pre-order), depth-first (in-order), and breadth-first order.

3 atHome

Write a function showTree that gives a nice representation as a String for a given tree. Every leaf should be placed on a different line (separated by "\n"). Leaves that are deeper in the tree should be further to the right than leaves higher in the tree.

4 inClass

Write a function mapTree and a function foldTree that work on a Tree, analoguous to map and foldr on lists. Also give the type of these functions.

5 inClass

Write a function height, that computes the amount of levels in a Tree. Give a definition using recursion, and a different definition using foldTree.

6 atHome

Suppose that a tree t has height n. What is the minimal and maximal amount of leaves that t could have?

7 atHome

Write a function that computes all paths of type [a] from the root up to a leaf for a tree of type Tree a.

8 atHome

Write a function that computes a list of nodes that occur on one of the longest paths from the root up to a leaf. Try to keep the solution linear with respect to the size of the tree.

9 atHome

Write mapTree using foldTree

10 inClass

Write a function extractMin that removes the smallest element from a binary search tree. Returns the smallest element and the remainder of the tree.

11 inClass

Write a function delete that deletes an element from the tree. You can assume the element appears at most once. Your new tree should remain a binary search tree.

Hint: You may want to use the function extractMin you defined above.

12 inClass

Define a binary tree type LeafTree in which leaves store values of type a and internal nodes store values of type b

13 atHome

Define a function height that given a LeafTree computes the height of the LeafTree a b. Leaves have height one.

14 inClass

Define a function annotate, that given a LeafTree Int b labels every internal node with the minimum and maximum value appearing in the leaves in its subtree.

e.g.

Node (Node (Leaf 3) "left" (Leaf 5))
     "root"
     (Leaf 1)

->

Node (Node (Leaf 3) (3,5) (Leaf 5))
     (1,5)
     (Leaf 1)

15 atHome

Write a function withDepth that annotates the tree by its depth. The depth of a node v is the length of the path from the root to v.

16 atHome

Write a function trimWhen :: (a -> Bool) -> (b -> Bool) -> LeafTree a b -> LeafTree (LeafTree a b) b that ‘trims’ the subtree depending on two predicates p :: a -> Bool and q :: b -> Bool . In particular, predicate p x returns True if and only if we should trim the leaf storing some value x and q y returns True if and only if the subtree whose root stores a y should be trimmed.

17 atHome

Write a function bimapTree :: (a -> c) -> (b -> d) -> LeafTree a b -> LeafTree c d.

18 atHome

Write a function trim :: Int -> LeafTree a b -> LeafTree (Maybe (LeafTree a b) b) that trims a tree at the given depth.

19 atHome

Define a Tree type TTTree a that models trees in which

• the leaves store values of type a,
• internal nodes either have 2 or 3 children, and
• internal nodes store an ‘Int’ denoting the size (number of leaves) in the subtree.

20 atHome

Define a function insert that inserts a new element in a TTTree, while maintaining the subtree size invariant, and while keeping the height low (e.g. try to avoid increasing the height if possible).

21 atHome

Define mapTTTree and foldTTTree functions for your TTTree data type.

22 atHome

Define function sized that, given an Int \(n\), returns all subtrees of size \(n\).

23 atHome

It is not possible to write the sized function directly using foldTTTree. However, we can use foldTTTree to do most of the work; that is, we can define a function sized' using foldTTTree such that

sized   :: Int -> TTTree a -> [TTTree a]
sized n = snd . sized' n

write the function sized'

24 atHome

A TTTree is valid if all root to leaf paths are equally long. Write a function height that computes the height of a TTtree if it is valid. Think about a suitable type for your function.

25 Red-Black Trees atHome

Write a function validRBTree :: RBTree a -> Bool that checks if a given RBTree a satisfies all red-black tree properties.

26 atHome

Consider the following data type of binary trees BST a that we intend to use to implement binary search trees. We will store “real” elements (the elements we care about) only in the Leaves of the tree. The a field in a Node is used only as a routing element (to guide searches).

data BST a = Leaf a
           | Node (BST a) a (BST a)
           deriving (Show,Read,Eq)

We can compute the elements we care about of such a tree as follows:

elems :: BST a -> [a]
elems (Leaf x) = [x]
elems (Node l _ r) = elems l ++ elems r

An example of such a trees we will care about is

exampleTree = Node (Node (Leaf 1) 3 (Node (Leaf 4) 6 (Leaf 7))) 8 (Node (Leaf 9) 10 (Leaf 13))

Then elems exampleTree = [1, 4, 7, 9, 13]

Here, the only purpose of the element 8, for example, is to signal that all the elements in the left subtree are \(\leq 8\) and that all the elements in the right subtree are \(> 8\).

The question: write a function complete that constructs a complete balanced binary search tree out of an sorted list of \(2^h\), with \(h \geq 0\), elements (with those elements in the same order as given.).

Bonus: Write complete so that it runs in linear time.

27 atHome

Give the type of a function delete, such that, given an element a and tree t, delete a t looks whether a is present in t and if so, removes a from t. The function delete should always be able to produce a valid element of the result type, i.e. it may not produce an error.

28 atHome

Please implement the above function delete.

29 atHome

Use higher order functions (i.e. foldr, foldl', map, filter) to write a function batchDelete that removes all elements from a given list from a tree. Give the type of this function as well.