isBalanced.hs

data BTree a = BLeaf | BNode (BTree a) (BTree a)

count :: BTree a -> Integer
count BLeaf = 1
count (BNode l r) = count l + count r

foldTree f z BLeaf = z
foldTree f z (BNode l r) = f (foldTree f z l) (foldTree f z r)

isBalancedTree' :: BTree a -> Bool
isBalancedTree' BLeaf = True
isBalancedTree' (BNode l r) = 
    let (m, n) = (count l, count r)
    in 3 * (m + 1) >= n + 1 
    && 3 * (n + 1) >= m + 1 
    && isBalancedTree' l 
    && isBalancedTree' r

isBalancedTree :: BTree a -> Bool
isBalancedTree = fst . foldTree f c
    where
        c = (True, 1)
        f (lb, n) (rb, m) = (3 * (m + 1) >= n + 1 && 3 * (n + 1) >= m + 1 && lb && rb, n + m)