Implementing a binary search tree data structure

A binary search tree restricts an order property on a binary tree. This order property requires that among every node, the nodes in the left subtree must not be greater, and that the nodes in the right subtree must not be less than the current node.

How to do it...

1. Create a binary BSTree module to expose our binary search tree data structure. Insert the following code in a file called BSTree.hs:

   module BSTree (insert, find, single) where

2. Define the data structure for a binary tree:

   data Tree a = Node	{value	:: a
                      , left   :: (Tree a)
                      , right  :: (Tree a)}
                | Null
                deriving (Eq, Show)

3. Define a convenience function to create a one-node tree:

   single :: a -> Tree a
   
   single n = Node n Null Null

4. Implement a function to insert new values in the binary search tree:

   insert :: Ord a => Tree a -> a -> Tree a
   
   insert (Node v l r) v'
     | v' < v      = Node v (insert l v') r
     | v' >...