Trees

Binary Search Trees

Consider the following Binary Tree type

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

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

   elemTree :: Ord a => a -> Tree a -> Bool
   elemTree q t = succOf q t == q
   
   -- or directly:
   
   elemTree :: Ord a => a -> Tree a -> Bool
   elemTree _ Leaf = False
   elemTree q (Node l x r) | q < x     = elemTree q l
                           | q == x    = True
                           | otherwise = elemTree q r

2. 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.

   traverseTree                      :: ([a] -> a -> [a] -> [a]) -> Tree a -> [a]
   traverseTree _       Leaf         = []
   traverseTree combine (Node l x r) =
     combine (traverseTree combine l) x (traverseTree  combine r)
   
   preOrderTraversal :: Tree a -> [a]
   preOrderTraversal = traverseTree (\l x r -> x : (l ++ r))
   
   inOrderTraversal :: Tree a -> [a]
   inOrderTraversal = traverseTree (\l x r -> l ++ (x : r))

3. 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. 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.

   mapTree                :: (a -> b) -> Tree a -> Tree b
   mapTree _ Leaf         = Leaf
   mapTree f (Node l x r) = Node (mapTree f l) (f x) (mapTree f r)
   
   foldTree                  :: (b -> a -> b -> b) -> b -> Tree a -> b
   foldTree _ z Leaf         = z
   foldTree f z (Node l x r) = f (foldTree f z l) x (foldTree f z r)

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

   height = foldTree (\l _ r -> 1 + l `max` r) 1

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

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

   paths              :: Tree a -> [[a]]
   paths Leaf         = [[]]
   paths (Node l x r) = map (x:) (paths l) ++ map (x:) (paths r)

8. 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. Write mapTree using foldTree

   mapTree f = foldTree (\l x r -> Node l (f x) r) Leaf

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

    extractMin              :: Tree a -> Maybe (a, Tree a)
    extractMin Leaf         = Nothing
    extractMin (Node l k r) = case extractMin l of
                                Nothing     -> Just (k, r)
                                Just (m,l') -> Just (m, Node l' k r)

11. 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.

    delete                :: Ord a => a -> Tree a -> Tree a
    delete _ Leaf         = Leaf
    delete x (Node l k r) = case x `compare` k of
                              LT -> Node (delete x l) k r
                              EQ -> case extractMin r of
                                      Nothing     -> l
                                      Just (m,r') -> Node l m r'
                                        -- we replace k by its successor.
                              GT -> Node l k (delete x r)

Trees with values in the Leaves

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

   data Tree a b = Leaf a
                 | Node (Tree a b) b (Tree a b)
                 deriving (Show,Eq)

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

   height              :: Tree a b -> Int
   height (Leaf _)     = 1
   height (Node l _ r) = 1 + max (height l) (height r)

3. Define a function annotate, that given a Tree b Int 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)

   annotate   :: Tree b Int -> Tree (Int,Int) Int
   annotate t = case annotate' t of
                  (t',_,_) -> t'
   
   -- | Computes the annotated tree, as well as the minimum and maximum in the tree
   annotate'              :: Tree b Int -> (Tree (Int,Int) Int, Int, Int)
   annotate' (Leaf x)     = (Leaf x, x, x)
   annotate' (Node l _ r) = let (l',lmin,lmax) = annotate' l
                                (r',rmin,rmax) = annotate' r
                                mi             = min lmin rmin
                                ma             = max lmax rmax
                            in (Node l' (mi,ma) r', mi, ma)

4. 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.

   withDepth :: Tree a b -> Tree (a,Int) (b,Int)
   withDepth = withDepth' 0
   
   withDepth'                :: Int -> Tree a b -> Tree (a,Int) (b,Int)
   withDepth' d (Leaf x)     = Leaf (x,d)
   withDepth' d (Node l x r) = Node (withDepth' (d+1) l) (x,d) (withDepth' (d+1) r)

5. Write a function trimWhen :: (a -> Bool) -> (b -> Bool) -> Tree a b -> Tree (Tree 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.

   trimWhen       :: (a -> Bool) -> (b -> Bool) -> Tree a b
                  -> Tree (Maybe (Tree a b)) b
   trimWhen p q t = case t of
                      Leaf x | p x           -> Leaf (Just t)
                             | otherwise     -> Leaf Nothing
                      Node l y r | q y       -> Leaf (Just t)
                                 | otherwise -> Node (trimWhen p q l) y (trimWhen p q r)

6.write a function bimapTree :: (a -> c) -> (b -> d) -> Tree a b -> Tree c d.

bimapTree       :: (a -> c) -> (b -> d) -> Tree a b -> Tree c d
bimapTree f g t = case t of
                    Leaf x     -> Leaf (f x)
                    Node l x r -> Node (bimapTree f g l) (g x) (bimapTree f g r)

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

   trim   :: Int -> Tree a b -> Tree (Maybe (Tree a b)) b
   trim d = bimapTree f fst . trimWhen p p . withDepth
     where
       p        :: (c,Int) -> Bool
       p (_,d') = d' == d
   
       f Nothing  = Nothing
       f (Just t) = Just $ bimapTree fst fst t

TT-Trees

1. 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.

     data TTTree a = Leaf a
                   | Node2 Int (TTTree a) (TTTree a)
                   | Node3 Int (TTTree a) (TTTree a) (TTTree a)

2. 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).

3. Define mapTTTree and foldTTTree functions for your TTTree data type.

   foldTTTree           :: (a -> b) -> (Int -> b -> b -> b) -> (Int -> b -> b -> b -> b) -> TTTree a -> b
   foldTTTree f g2 g3 t = case t of
                            Leaf x        -> f x
                            Node2 s l r   -> g2 s (foldTTTree f g2 g3 l) (foldTTTree f g2 g3 r)
                            Node3 s l m r -> g3 s (foldTTTree f g2 g3 l) (foldTTTree f g2 g3 m) (foldTTTree f g2 g3 r)
   
   mapTTTree f = foldTTTree (Leaf . f) Node2 Node3

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

5. 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'

   sized   :: Int -> TTTree a -> (TTTRee a, [TTTree a])
   sized n = foldTTTree f g2 g3
     where
       singleton s t = if n == s then [t] else []
   
       f x = let t = Leaf x
             in (t,singleton s t)
   
       g2 s (l,ls) (r,rs) = let t = Node2 s l r
                            in (t, singleton s t ++ ls ++ rs)
   
       g3 s (l,ls) (m,ms) (r,rs) = let t = Node3 s l m r
                                   in (t, singleton s t ++ ls ++ ms ++ rs)

6. 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.

   height :: TTTree a -> Maybe Int
   height = foldTTTree (\_          -> Just 0)
                       (\_ lh rh    -> inc $ lh <.> rh)
                       (\_ lh mh rh -> inc $ lh <.> mh <.> rh)
     where
       inc Nothing  = Nothing
       inc (Just h) = Just (h+1)
   
       Nothing <.> _                   = Nothing
       Just h  <.> Nothing             = Nothing
       Just h  <.> Just hr | h == hr   = Just h
                           | otherwise = Nothing

Red-Black Trees

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

Complete Binary Trees

Consider the following data type of binary trees Tree 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 Tree a = Leaf a
            | Node (Tree a) a (Tree a)
            deriving (Show,Read,Eq)

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

elems :: Tree 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\).

1. 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.).

   -- | This runs in O(n\log n) time.
   complete :: [a] -> Tree a
   complete [x] = Leaf x
   complete xs  = let (ls,rs) = splitAt (n `div` 2) xs
                      n       = length xs
                  in Node (complete ls) (last ls) (complete rs)

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

2. 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.

   delete :: Ord a => a -> Tree a -> Maybe (Tree a)

3. Please implement the above function delete.

   delete x t = case t of
     Leaf y | x == y        -> Nothing
            | otherwise     -> Just t
     Node l k r | x <= k    -> Just $ case delete x l of
                                 Nothing -> r
                                 Just l' -> Node l' k r
                | otherwise -> Just $ case delete x r of
                                 Nothing -> l
                                 Just r' -> Node l k r'

4. 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.

   batchDelete      :: Ord a => [a] -> Tree a -> Maybe (Tree a)
   batchDelete xs t = foldr (\x mt -> mt >>= \t -> delete x t) (Just t) xs
     where
       -- This funny operator is called "bind" and is actually defined in
       -- the prelude. It is the part of the Monad instance/definition of
       -- the 'Maybe' type.
       (>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b
       Nothing  >>= _ = Nothing
       (Just x) >>= f = f x