-- Question 1

data Tree a = Node a (Tree a) (Tree a)

  | Leaf



instance Eq a => Eq (Tree a) where

  Leaf == Leaf = True

  (Node val left right) == Leaf = False

  Leaf == (Node val left right) = False

  (Node val1 left1 right1) == (Node val2 left2 right2) =

    case val1 == val2 of

      True -> left1 == left2 && right1 == right2

      _ -> False



-- Question 2

instance Functor Tree where

  fmap f Leaf = Leaf

  fmap f (Node val left right) =

    (Node (f val) (fmap f left) (fmap f right) )



--Question 3

bstInsert :: Ord a => Tree (a, Int) ->  a -> Tree (a, Int)

bstInsert Leaf n = (Node (n, 1) Leaf Leaf)

bstInsert (Node (val, num) left right) n =

  case compare n val of

    GT -> case right of

      Leaf -> (Node (val, num) left (Node (n,1) Leaf Leaf))

      _ -> (Node (val,num) left (bstInsert right n))

    LT -> case left of

      Leaf -> (Node (val, num) (Node (n, 1) Leaf Leaf) right)

      _ -> (Node (val,num) (bstInsert left n) right)

    _ -> (Node (val, num+1) left right)



--Question 4

bstLookup :: Ord a => Tree (a, Int) -> a -> Int

bstLookup Leaf n = 0

bstLookup (Node (val, num) left right) n =

  case compare n val of

    GT -> bstLookup right n

    LT -> bstLookup left n

    _ -> num



--Question 5



bstRemove :: Ord a=> Tree (a, Int) -> a -> Maybe (Tree (a,Int))

bstRemove Leaf n = Nothing



bstRemove (Node (val, num) left right) n =

  case compare n val of

    GT -> case (bstRemove right n) of

      Nothing -> Nothing

      Just removeR -> Just (Node (val,num) left removeR)

    LT -> case (bstRemove left n) of

      Nothing -> Nothing

      Just removeL -> Just (Node (val,num) removeL right)

    _ -> case num > 1 of

      True -> Just (Node (val, num-1) left right)

      _ -> case (Node (val,num) left right) of

        (Node (val,num) Leaf Leaf) -> Just Leaf

        (Node (val,num) left Leaf) -> Just left

        (Node (val,num) Leaf right) -> Just right

        _ -> let mini = bstFindMin right in

          case (bstRemove right mini) of

          Just removeR ->Just (Node (mini, (bstLookup right mini) ) left removeR)

          _ -> Nothing









bstFindMin :: Ord a => Tree(a,Int) -> a

bstFindMin (Node (val, num) left right) =

  case left of

    Leaf -> val

    _ -> bstFindMin left



--Question 6

instance Show a => Show (Tree a) where

  show Leaf = "Leaf"

  show myTree =

    myShow 0 myTree





myShow :: Show a => Int -> Tree a -> String

myShow n Leaf = ""

myShow 0 (Node val left right) =

  "Node " ++ show val ++ "\n" ++ (myShow 2 left) ++ (myShow 2 right)

myShow n (Node val left right) =

  (stringMultiply " " n) ++ "Node " ++ show val ++ "\n" ++ (myShow (n+2) left) ++ (myShow(n+2) right)





stringMultiply :: String -> Int -> String

stringMultiply s 0 = ""

stringMultiply s n = s ++ stringMultiply s (n-1)