-- Example: Binary tree
data Tree a = Empty | Node a (Tree a) (Tree a)
              deriving (Eq, Show)

-- assumption: < is a linear ordering

find :: Ord a => a -> Tree a -> Bool
find _ Empty  =  False
find x (Node a l r)
  | x == a     =  True
  | x < a      =  find x l
  | otherwise  =  find x r

insert :: Ord a => a -> Tree a -> Tree a
insert x Empty  =  Node x Empty Empty
insert x (Node a l r)
  | x == a     =  Node a l r
  | x < a      =  Node a (insert x l) r
  | otherwise  =  Node a l (insert x r)

delete :: Ord a => a -> Tree a -> Tree a
delete x Empty = Empty
delete x (Node a l r)
  | x == a     =  combine l r
  | x < a      =  Node a (delete x l) r
  | otherwise  =  Node a l (delete x r)

combine :: Tree a -> Tree a -> Tree a
combine Empty r  =  r
combine l Empty  =  l
combine l r      =  Node m l r'  where (m,r') = delMin r

-- delMin t = (leftmost/minimal element of t, t without that element)
delMin :: Tree a -> (a, Tree a)
delMin (Node a Empty r)  = (a, r)
delMin (Node a l     r)  = (m, Node a l' r)  where (m,l') = delMin l