-- Ex1

data BTree a = Nil | Node a (BTree a) (BTree a)

sumTree :: BTree Int -> Int
sumTree Nil = 0
sumTree (Node n bt1 bt2) = n + sumTree bt1 + sumTree bt2

instance Eq a => Eq (BTree a) where
  Nil == Nil = True
  (Node n1 bt11 bt12) == (Node n2 bt21 bt22) = (n1 == n2) && (bt11 == bt21) && (bt12 == bt22)

-- Ex2

getLevelsTree :: BTree a -> BTree (a,Int)
getLevelsTree bt = calc bt 0
  where
    calc Nil _ = Nil
    calc (Node n bt1 bt2) l = (Node (n,l) (calc bt1 (l + 1)) (calc bt2 (l + 1)))

-- Ex3

mapTree :: (a -> b) -> BTree a -> BTree b
mapTree _ Nil = Nil
mapTree f (Node n bt1 bt2) = (Node (f n) (mapTree f bt1) (mapTree f bt2))

-- Ex4

data Color = Red | Green | Blue
           deriving (Read, Show, Eq)

maxDepthBlueNode :: BTree Color -> Int
maxDepthBlueNode bt = calc 0 bt
  where
    calc _ Nil = 0
    calc l (Node col bt1 bt2)
      | col == Blue = max l $ max (calc (l+1) bt1) (calc (l+1) bt2)
      | otherwise = max (calc (l+1) bt1) (calc (l+1) bt2)

-- Ex5

maxDepthNode :: BTree Color -> Color -> Int
maxDepthNode bt col = calc col 0 bt
  where
    calc _ _ Nil = 0
    calc clr l (Node col bt1 bt2)
      | col == clr = max l $ max (calc clr (l+1) bt1) (calc clr (l+1) bt2)
      | otherwise = max (calc clr (l+1) bt1) (calc clr (l+1) bt2)

-- Ex6

data NTree a = NNil | NNode a [NTree a]

size :: NTree a -> Int
size NNil = 0
size (NNode e ch) = foldr (\el acc -> acc + size el) 1 ch

-- Ex7

l1 NNil _ = 0
l1 (NNode elem _) e = abs (elem - e)

isGracious :: NTree Int -> Bool
isGracious NNil = True
isGracious (NNode e ch) = all even (map (\n -> l1 n e) ch) && all isGracious ch

-- main

inorder :: BTree a -> [a]
inorder Nil = []
inorder (Node n bt1 bt2) = inorder bt1 ++ [n] ++ inorder bt2

t1 :: BTree Int                       --     1                  
t1 = Node 1 (Node 2 (Node 5 Nil Nil)  --    / \
                    Nil)              --   2   3
            (Node 3 (Node 7 Nil Nil)  --  /   / \
                    (Node 6 Nil Nil)) -- 5   7   6

colorTree :: BTree Color                                        --            Blue
colorTree = Node Blue (Node Red (Node Green Nil Nil) Nil)       --           /    \
                      (Node Red (Node Blue (Node Green Nil Nil) --        Red      Red
                                           (Node Red Nil Nil))  --        /        /  
                                Nil)                            --     Green     Blue  
                                                                --               /   \
                                                                --            Green  Red

nTree1 :: NTree Int                             --       1
nTree1 = NNode 1 [(NNode 2 [(NNode 3 [NNil]),   --      / \
                            (NNode 4 [NNil]),   --     2   6
                            (NNode 5 [NNil])]), --    /|\  |
                  (NNode 6 [(NNode 7 [NNil])])] --   3 4 5 7

nTree2 :: NTree Int                              --       0
nTree2 = NNode 0 [(NNode 6 [NNil]),              --      / \
                  (NNode 4 [(NNode 8 [NNil]),    --     6   4
                            (NNode 2 [NNil]),    --        /|\
                            (NNode 12 [NNil])])] --       8 2 12

main :: IO()
main = do
  print(show(sumTree t1) ++ show(t1 == t1))
  print(inorder(getLevelsTree t1))
  print(inorder(mapTree (show) t1))
  print(maxDepthBlueNode colorTree)
  print(maxDepthNode colorTree Red)
  print(size nTree1)
  print(show(isGracious nTree1) ++ " " ++ show(isGracious nTree2))