module type BST = 
sig
        type 'a tree (* abstract tree type *)   
        val create : 'a tree
        val insert : 'a tree -> 'a -> 'a tree           
        val contains : 'a tree -> 'a -> bool        
        val map : ('a -> 'a) -> 'a tree -> 'a tree 
        val fold : ('b -> 'a -> 'b) -> 'b -> 'a tree -> 'b
end

module BSTImpl =
struct    

    (* define tree type consisting of inner nodes and leaf nodes *)
    type 'a tree = Node of ('a * 'a tree * 'a tree) | Leaf
    
    (* create an empty tree *)
    let create = Leaf
    ;;
    
    (* create new tree by inserting v into n *)
    let rec insert n v = match n with
        | Leaf -> Node (v, Leaf, Leaf)
        | Node (x, left, right) ->
            if x < v then Node (x, (insert left v), right)
            else if x > v then Node (x, left, (insert right v))
            else n
    ;;
    
    (* return true if n contains v *)
    let rec contains n v = match n with
        | Leaf -> false
        | Node (x, left, right) ->
            if x < v then contains left v
            else if x > v then contains right v
            else true
    ;;
    
    (* create new tree by applying f to the values of n *)
    let rec map f n = match n with
        | Leaf -> Leaf
        | Node (x, left, right) -> Node ((f x), (map f left), (map f right))
    ;;    
    
    (* perform fold operation by in-order traversal of n *)
    let rec fold f a n = match n with
        | Leaf -> a
        | Node (x, left, right) -> 
            fold f (f (fold f a left) x) right
    ;;    
end

module Bst : BST = BSTImpl;;

let tree = Bst.create;;
let tree = Bst.insert tree 50;;
let tree = Bst.insert tree 25;;
let tree = Bst.insert tree 75;;
let tree = Bst.insert tree 0;;
let tree = Bst.insert tree 100;;
let tree = Bst.insert tree 40;;
let tree = Bst.insert tree 60;;
let tree = Bst.map (fun x -> x * 2) tree;;
Bst.fold (fun a x -> x::a) [] tree;;