Ocaml Functional Programming Tree
You have the right idea, but you didn't quite know how to get there.  You don't need that traverse function to operate on the left or right lists.  Just bind them to separate variables through a simple let in expression and you can add the items to each of the lists.

let rec unzip = function
    | (x, y)::t -&gt; let l, r = unzip t in (x::l, y::r)
    | []        -&gt; ([], [])