module BTree where

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

size :: BTree a -> Integer
size Empty        = 0
size (Node _ l r) = size l + size r + 1

height :: BTree a -> Integer
height Empty        = 0
height (Node _ l r) = max (height l) (height r) + 1

fromList :: [a] -> BTree a
fromList []     = Empty
fromList (x:xs) = Node x Empty (fromList xs)

make :: [a] -> BTree a
make [] = Empty
make xs = Node z (make ys) (make zs)
  where
    m = length xs `div` 2
    (ys, z:zs) = splitAt m xs

searchTree :: Ord a => [a] -> BTree a
searchTree = foldr insert Empty
  where
    insert x Empty = Node x Empty Empty
    insert x (Node y l r)
      | x < y     = Node y (insert x l) r
      | otherwise = Node y l (insert x r)
        
flatten :: BTree a -> [a]
flatten Empty        = []
flatten (Node x l r) = flatten l ++ [x] ++ flatten r