binaryTrees[0] = {};
binaryTrees[1] = {leaf};
binaryTrees[n_Integer] := Flatten @ Table[vtx[t1, t2],
    {m, 1, n-1}, {t1, rootedBinaryTrees[n-m]}, {t2, rootedBinaryTrees[m]}];

enumeratedTrees = Block[{i = 1}, # /. leaf :> i++] & /@ binaryTrees[9];
operatorPermutations = Tuples[Inactive /@ {Plus, Subtract, Times, Divide}, 8];
solutions = {};

Do[
  s = Select[
    Table[Block[{i = 1},
      tree /. vtx :> operatorPermutations[[m, i++]]],
     {tree, enumeratedTrees}],
    Activate[#] == 2015 &];
  If[Length[s] > 0, Print[s]; AppendTo[solutions, {m, s}]];
  If[Mod[m, 500] == 0, Print[m]],
  {m, 65536}];
Export["solutions_raw.txt", solutions];

stringify[Inactive[head_][a_, b_]] := ToString@StringForm["(`` `` ``)",
    stringify[a],
    head /. {Plus -> "+", Subtract -> "-", Times -> "*",
      Divide -> "/"},
    stringify[b]];
stringify[n_Integer] := ToString[n];

Export["solutions_formatted.txt",
  stringify /@ Flatten[Last /@ solutions]];