datatype Tree = Branch of Tree * Tree | Node of string;

fun collect (nil : a' list list) : a' list = nil
  | collect (x::xs) = x@collect(xs);

fun insertVariable variableToInsert : string ([] : string list) : string list list = [[variableToInsert]]
  | insertVariable variableToInsert (x::xs) =
      (variableToInsert::x::xs)::(map(fn (y) => x::y)(insertVariable(variableToInsert)(xs)));

fun getPermutations (nil : string list) : string list list = [[]]
  | getPermutations (x::xs) =
      collect ((map (insertVariable (x)))(getPermutations(xs)));

fun buildTreePossibilities (nil : Tree list, nil : Tree list) : Tree list = nil
  | buildTreePossibilities (leftTrees, nil) = nil
  | buildTreePossibilities (leftTrees, right::rightTrees) =
      let
        fun addRightPossibilities (nil, currRight) = nil
          | addRightPossibilities (l::lefts, currRight) : Tree list =
          Branch(l, currRight)::addRightPossibilities(lefts, currRight);
      in
        addRightPossibilities(leftTrees, right)@buildTreePossibilities(leftTrees, rightTrees)
      end;

fun buildTrees (nil : string list list) : Tree list = nil
  | buildTrees (x::xs) =
    let
      fun treeFromPerm(nil, n) : Tree list = nil
        | treeFromPerm(list, n) =
            if length(list) = 1 then [Node(concat(list))]
            else if n = (length(list)) then nil
            else (buildTreePossibilities(treeFromPerm(List.take(list, n), 1),treeFromPerm(List.drop(list, n), 1)))@treeFromPerm(list, n + 1)
    in
      treeFromPerm(x, 1)@buildTrees(xs)
    end;

buildTrees(getPermutations(["a", "b", "c", "d", "e"]));