tree balance

gistfile1.hs

{-# LANGUAGE GADTs, KindSignatures #-}
data Tree :: * where
Leaf :: Int -> Tree
Node :: Tree -> Tree -> Tree
    deriving (Show,Eq,Ord)

-- Write a function that sums the leaf values in a tree
summation :: Tree -> Int
summation (Leaf v) = v
summation (Node l r) = (summation l) + (summation r)

-- Write a function that finds the depth of a tree
depth :: Tree -> Int
depth (Leaf _) = 0
depth (Node l r) = 1 + max (depth l) (depth r)

list :: Tree -> [Int]
list (Leaf v) = [v]
list (Node l r) = list l ++ list r

-- Write a function that balances a binary tree
balance :: Tree -> Tree
balance t = genBalancedTree $ map Leaf $ list t
    where genBalancedTree [x] = x
          genBalancedTree (x:y:zs) = genBalancedTree $ reverse $ Node x y : zs