Haskell monad- and error-handling-style
There are couple of points that I'd suggest:


Be sure to always include types for top-level functions. Without them, the code becomes very quickly unreadable. For example, would you know what ins does and what is its type, if you didn't write it yourself? In many cases you can immediately judge what a function does just looking at its name and its type.
If you do

  | x &lt; e  = ...
  | x == y = ...
  | otherwise = ...


you're performing the comparison twice. In most cases this shouldn't be a problem, but if writing

case compare x e of
  LT -&gt; ...
  EQ -&gt; ...
  GT -&gt; ...


will compare only once, and also allows the compiler to do more optimizations.
This isn't a problem, just a note: Be aware that fastInsert trades speed for lazyiness. If you examine the root of the tree returned by a fastInsert call, the tree must be examined to check if it contains the inserted element or not. Under most circumstances you wouldn't mind that.
There is no need for ins to take Maybe (Tree e) as the argument, only to apply &gt;&gt;= on it. Most monadic functions take pure arguments and return a monadic one.
It's often convenient to use functions from Control.Applicative to lift pure functions/values to monadic computations. In particular pure, &lt;$&gt; and &lt;*&gt;. See also Functor, Applicative and Monad.


I wasn't sure what error handling you have in mind, as these operations should never fail.

The updated program:

import Control.Applicative
import Data.Maybe

data Tree e = Leaf | T (Tree e) e (Tree e) deriving Show

empty = Leaf

insert :: (Ord e) =&gt; e -&gt; Tree e -&gt; Tree e
insert x Leaf = T Leaf x Leaf
insert x tree@(T l e r) = case compare x e of
  EQ -&gt; tree
  LT -&gt; T (insert x l) e r
  GT -&gt; T l e (insert x r)

ins :: (Ord e) =&gt; e -&gt; Tree e -&gt; Maybe (Tree e)
ins x Leaf = return $ T Leaf x Leaf
ins x tree@(T l e r) = case compare x e of
  EQ -&gt; Nothing
  LT -&gt; (\l' -&gt; T l' e r) &lt;$&gt; ins x l
-- you could also write a point-free version, if you like,
-- which better preserves the order of arguments
--  LT -&gt; T &lt;$&gt; ins x l &lt;*&gt; pure e &lt;*&gt; pure r
  GT -&gt; T l e &lt;$&gt; ins x r

fastInsert :: (Ord e) =&gt; e -&gt; Tree e -&gt; Tree e
fastInsert x t =
  fromMaybe t $ ins x t