-- Ex1

data BTree a = Nil | Node a (BTree a) (BTree a)
               deriving (Eq,Show,Read)

size :: BTree a -> Int
size Nil = 0
size (Node n bt1 bt2) = 1 + size bt1 + size bt2

cntheight :: BTree a -> Int
cntheight Nil = 0
cntheight (Node n bt1 bt2) = 1 + max (height bt1) (height bt2)

height :: BTree a -> Int
height bt = cntheight bt - 1

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

sumLeaves :: BTree Int -> Int
sumLeaves Nil = 0
sumLeaves (Node n bt1 bt2)
  | bt1 == Nil && bt2 == Nil = n
  | otherwise = sumLeaves bt1 + sumLeaves bt2

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

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

t2 :: BTree Int                                  --    5
t2 = Node 5 (Node 3 Nil Nil)                     --   / \
                   (Node 4 (Node 5 Nil Nil)      --  3   4
                               (Node 7 Nil Nil)) --     / \
                                                 --    5   7

-- Ex2

getLevel :: Int -> BTree a -> [a]
getLevel _ Nil = []
getLevel l (Node n bt1 bt2)
  | l == 0 = [n]
  | otherwise = getLevel (l - 1) bt1 ++ getLevel (l - 1) bt2

-- Ex3

avg :: [Int] -> Double
avg [] = 0
avg l = fromIntegral(sum l) / fromIntegral(length l)

average :: BTree Int -> Double
average bt = avg (inorder bt)

-- Ex4

mirrorTree :: BTree a -> BTree a
mirrorTree Nil = Nil
mirrorTree (Node n bt1 bt2) = (Node n (mirrorTree bt2) (mirrorTree bt1))

main :: IO()
main = do
  print("t1: " ++ show (size t1) ++ " " ++ show (height t1) ++ " " ++ show(sumTree t1) ++ " " ++ show(sumLeaves t1) ++ " " ++ show(inorder t1))
  print("t2: " ++ show (size t2) ++ " " ++ show (height t2) ++ " " ++ show(sumTree t2) ++ " " ++ show(sumLeaves t2) ++ " " ++ show(inorder t2))
  print(show(getLevel 0 t1) ++ show(getLevel 1 t1) ++ show(getLevel 2 t1))
  print(show(getLevel 0 t2) ++ show(getLevel 1 t2) ++ show(getLevel 2 t2))
  print(average t1)
  print(average t2)
  print(inorder(mirrorTree t1))
  print(inorder(mirrorTree t2))