-- |
-- = A Module for Binary Trees.
module BTree where

-- | A binary tree is either 'Empty' or consists of a 'Note' with
--   at most two direct subtrees.
data BTree a = Empty | Node a (BTree a) (BTree a)
  deriving (Eq, Show, Read)

-- | The 'size' of a binary tree is the number of 'Node's it contains.
size :: BTree a -> Integer
size Empty        = 0
size (Node _ l r) = size l + size r + 1

-- | The 'height' of a binary tree is the length of the longest path
--   from the its root to one of its leafs.
height :: BTree a -> Integer
height Empty        = 0
height (Node _ l r) = max (height l) (height r) + 1

-- | Transforming a list into a binary tree of the same structure.
fromList :: [a] -> BTree a
fromList []     = Empty
fromList (x:xs) = Node x Empty (fromList xs)

-- | Building a balanced binary tree from a list.
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

-- | Building a binary search tree from a list.
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)
        
-- | Turning a binary tree into a list by inorder traversal of nodes.
flatten :: BTree a -> [a]
flatten Empty        = []
flatten (Node x l r) = flatten l ++ [x] ++ flatten r