tree.hs

data BST = Node Int BST BST | Empty deriving (Show)

find :: BST -> Int -> Bool
find Empty x = False
find (Node v l r) x
  | x < v = find l x
  | x > v = find r x
  | otherwise = True

insert :: BST -> Int -> BST
insert Empty x = Node x Empty Empty
insert (Node v l r) x
  | x < v     = Node v (insert l x) r
  | x > v     = Node v l (insert r x)
  | otherwise = error "Tried to insert duplicate"

delete :: BST -> Int -> BST
delete Empty x = Empty
delete (Node v l r) x
  | x == v = subsumeTree r l
  | x < v  = Node v (delete l x) r
  | x > v  = Node v l (delete r x)
  where
    subsumeTree Empty sub = sub
    subsumeTree (Node v l r) sub = Node v (subsumeTree l sub) r