-- Joshua Rodgers
-- COSC 3015
-- HW #12

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

-- Problem #3
leaf_count :: (Tree a) -> Int
leaf_count (Leaf a) = 1
leaf_count (Node l r) = (leaf_count l) + (leaf_count r)

balanced :: (Tree a) -> Bool
balanced (Leaf a) = True
balanced (Node l r) = let b = (leaf_count l) - (leaf_count r) in
                          if b > 1 || b < -1 then False
					      else True
-- Problem #4

balance [x] = (Leaf x)
balance (xs) = let (ys, zs) = halve xs in
                   (Node (balance ys) (balance zs))
                   where halve ws = splitAt (length xs `div` 2) ws

main = print (balanced (balance [1..2^10]))