Mapping a sorted Btree

#1

I created a simple sorted Btree and I’m wondering how you could create a map function for this data structure to ensure the order of the mapped data. I created a map func(below) and I’m wondering if this is a correct way of doing it.

module MyBtree =
  struct

    type 'a btree = Empty | Btree of ('a * 'a btree * 'a btree)

    let empty = Empty

    let rec add data bt =
      match bt with
      | Empty -> Btree(data, Empty, Empty)
      | Btree (d, left, right) ->
        if (data < d)
        then
          Btree(d, add data left, right)
        else if (data > d)
        then
          Btree(d, left, add data right)
        else
          bt

(*...*)

    let map func bt =
      let rec mapAux func bt newBt =
        match bt with
        | Empty -> newBt
        | Btree (d, left, right) ->
          mapAux func right (mapAux func left (add (func d) newBt)) in
      mapAux func bt empty

end