module Tree where

data Tree a = Node a (Tree a) (Tree a) | EmptyTree

leaf :: a -> Tree a
leaf v = Node v EmptyTree EmptyTree

treeToList :: Tree a -> [a]
treeToList EmptyTree = []
treeToList (Node v left right) = (treeToList left) ++ (v:(treeToList right))

mapTree :: (a -> b) -> Tree a -> Tree b 
mapTree _ EmptyTree           = EmptyTree
mapTree f (Node v left right) = Node (f v) (mapTree f left) (mapTree f right)

foldTree :: (a -> b -> b -> b) -> b -> Tree a -> b
foldTree _ init EmptyTree = init
foldTree f init (Node v left right) =
    f v (foldTree f init left) (foldTree f init right)

showsTree :: Show a => Tree a -> String -> String
showsTree EmptyTree s           = s
showsTree (Node v left right) s =
  "<"++showsTree left (shows v (showsTree right (">"++s)))

showTree :: Show a => Tree a -> String
showTree EmptyTree = "<>"
showTree tree      = showsTree tree ""

insert :: Ord a => a -> Tree a -> Tree a
insert v  EmptyTree = leaf v
insert v1 (Node v2 left right) | v1 < v2   = Node v2 (insert v1 left) right
                               | otherwise = Node v2 left (insert v1 right)

insertList :: Ord a => [a] -> Tree a -> Tree a
insertList []     tree = tree
insertList (a:as) tree = insertList as (insert a tree)

listToTree :: Ord a => [a] -> Tree a
listToTree = (flip insertList) EmptyTree