Mini Binary Tree "library"
Function Visibility

In the code there's some functions that seem to be intended for internal use only. To hide these from external modules you should have a "proper" module declaration that exports those functions you want to make "public".

module MyTree ( Tree(ETree, Node), tInsert, tFromListL, tFromListR, ... ) where


this allows you to hide (and change) implementation details of your exposed function.

Balancing Your Tree

Your algorithm to balance that tree is something along the lines of \$\mathcal{O}(3 * n)\$. That's bad compared to an almost constant time-effort when balancing in tree form. Then again why are you even exposing this functionality?

If you allow a tree to be unbalanced, you shouldn't expose an operation to balance it and vice versa. You should strongly consider extracting balanced behaviour into either a separate type and using instance to expose a common "interface" or extract this into a completely separate module.

Something like this:

class (Ord a) =&gt; Tree a where
    tInsert, tDelete :: a -&gt; Tree a -&gt; Tree a
    tElem :: a -&gt; Tree a -&gt; Bool
    tIsBalanced :: Tree a -&gt; Bool
    tSize, tDepth :: Tree a -&gt; Int
    tMin, tMax :: Tree a -&gt; a
    tToList :: Tree a -&gt; [a]

data BalancedTree a = Empty | Node (BalancedTree a) (BalancedTree a) a deriving (Show)

instance NormalTree BalancedTree where
-- | because we are an instance of NormalTree we can access tInsert'
    tInsert = balance . tInsert'
-- and so on and so forth

data NormalTree a = Empty | Node (Tree a) (Tree a) a deriving (Show)

instance Tree NormalTree where
    tInsert = tInsert'

    -- | default implementation for insert without balancing
    tInsert' :: a -&gt; Tree a -&gt; Tree a



  Note that I haven't even used this myself and I'm not sure whether
  this works. The code should give you a gist as to how this could /
  should work and isn't even intended to be syntactically correct.


This defines the "interface" of Tree in a class and then uses data types to implement said "interface". 

Errors In Expected Circumstances

When you call tMax or tMin respectively on an ETree (which would be better named as Empty) an error is raised. That's an IMO really ugly and declarative way of solving this. It'd be preferrable to have a pure function. This requires a small change to the type-signature:

tMin, tMax :: Ord o =&gt; Tree o -&gt; Maybe o


Which in turn allows you to do the following:

tMin Empty = Nothing
tMin (Node lT _ a) = case lT of 
    Empty -&gt; a
    (Node lT' _ _) -&gt; tMin lT'


This function is total and pure. As such it's much easier and cleaner to use.