-- BSTree.hs
{- Binary Search Tree with methods -}

data BSTree a = Empty | Branch (BSTree a) a (BSTree a)
        deriving (Show, Ord)

search v Empty = False
search v (Branch left x right)
       | v<x = search v left
       | v==x = True
       | v>x = search v right

insert v Empty = Branch Empty v Empty
insert v (Branch left x right) =
   if v<x then Branch (insert v left) x right
          else if v==x then Branch left v right
                       else Branch left x (insert v right)

{- 
   The following allows the infix equality test (==)
   between Binary Search Trees
-}

instance (Eq a) => Eq (BSTree a) where
  Empty == Empty   = True 
  (Branch l1 x r1) == (Branch l2 y r2) =
                      (l1 == l2) && (x==y) && (r1 == r2)
  _ == _ = False