On my journey to learning F#, I've run into a problem I cant solve. I have defined a custom type:

type BinTree = 
  | Node of int * BinTree * BinTree
  | Empty

I have made a function which takes a tree, traverses it, and adds the elements it visits to a list, and returns it:

let rec inOrder tree = 
 seq{
 match tree with
  | Node (data, left, right) ->
   yield! inOrder left
   yield  data;
   yield! inOrder right
  | Empty -> ()
 }
 |> Seq.to_list;

Now I want to create a function, similar to this, which takes a tree and a function, traverses it and applies a function to each node, then returns the tree:

mapInOrder : ('a -> 'b) -> 'a BinTree -> 'b BinTree

This seems easy, and it probably is! But I'm not sure how to return the tree. I've tried this:

let rec mapInOrder f tree = 
 match tree with
 | Node(data, left, right) ->
  mapInOrder f left
  Node(f(data), left, right)
  mapInOrder f right
 | Empty -> ()

but this returns a unit. I havent worked with custom types before, so I'm probably missing something there!