module COMPARISON =
  struct
   type comparison = Less | Equal | Greater
  module type COMPARABLE =
   sig
      type t
      val cmp : t -> t -> comparison
    end
end

module IntCmp : COMPARISON.COMPARABLE =
  struct
    include COMPARISON
    type t = int
    let cmp x y = if (x - y = 0) then Equal else
                    (if (x - y < 0) then Less else Greater)
end



module BST (C : COMPARISON.COMPARABLE) :
  sig
    type t
    type tree
    val add : t -> tree -> tree
    val del : t -> tree -> tree
    val createFromList : t list -> tree
  end = struct
  include COMPARISON
  type t = C.t
  type tree = Nil | Node of t * tree * tree
  let rec add (elm : t) = function
    | Nil -> Node (elm, Nil, Nil)
    | Node (e, l, r) -> if C.cmp elm e = Less
                        then Node (e, add elm l, r)
                        else Node (e, l, add elm r)

  let rec del_aux_left = function
    | Nil -> Nil
    | Node (_, l, Nil) -> l
    | Node (e, l, Node (e', l', Nil)) -> Node (e, l, l')
    | Node (e, l, r) -> Node (e, l, del_aux_left r)

  let rec del_aux_right = function
    | Nil -> Nil
    | Node (_, Nil, r) -> r
    | Node (e, Node (e', Nil, r'), r) -> Node (e, r', r)
    | Node (e, l, r) -> Node (e, del_aux_right l, r)

  let rec closestLeft default = function
    | Nil -> default
    | Node (e, _, Nil) -> e
    | Node (e, _, r) -> closestLeft default r

  let rec closestRight default = function
    | Nil -> default
    | Node (e, Nil, _) -> e
    | Node (e, l, _) -> closestLeft default l

  (* how to have lessthan and equal in scope *)
  let rec del (elm : t) = function
    | Nil -> Nil
    | Node (e, l, r) -> if C.cmp elm e = Equal
                        then (match l with
                             | Nil -> (match r with
                                       | Nil -> Nil
                                       | node -> Node (closestRight e node, l, del_aux_right r))
                             | node -> Node (closestLeft e node, del_aux_left node, r))
                        else (if C.cmp elm e = Less
                              then Node (e, del elm l, r)
                              else Node (e, l, del elm r))

  let rec createFromList_aux = function
    | [] -> Nil
    | x :: xs -> add x (createFromList_aux xs)

  let rec createFromList l = createFromList_aux (List.rev l)

end