
(**
 * RandomTree[n]
 * 
 * Generates a labelled tree with n vertices at random.
 * Every tree has the same (pseudo)probability of being
 * the result of this method.
 **)
RandomTree[n_Integer] := 
  Random[Integer, {1, n^(n-2)}] // (* create a random number *)
  Number2Tuple[n, n-2, #]& // (* convert it to a tuple *)
  UnPruefer[n, #]& // (* convert the tuple to a tree *)
  Tree2Expr; (* express the tree as an expression tree *)

(**
 * Number2Tuple[n, m, t]
 * 
 * Maps the number t to the element of [n]^[m] it encodes. 
 * t is assumed to be an integer between 1 and n^m inclusively.
 **)
Number2Tuple[n_Integer, m_Integer, t_Integer] := 
  Module[ {i},

  Table[1 + Quotient[Mod[t-1, m^i], m^(i-1)], {i, 1, m}]
];

(**
 * UnPruefer[n, pi]
 *
 * Given a tuple pi in [n]^[n-2], this method generates the tree
 * for which Pruefer gives pi.
 *
 * The tree is returned as a set of pairs encoding the edges of the 
 * tree. The vertex set is always [n]. 
 **)
UnPruefer[n_Integer, pi_List] := 
  Module[ {edges, e, i, N, found},

  N = Range[1, n-1];
  edges = {{Last[pi], n}};
  found = {};

  Do[
    e = Min @@ Complement[N, found, Drop[pi, i-1]];
    AppendTo[found, e];
    AppendTo[edges, Sort[{pi[[i]], e}]];
  , {i, 1, n-2}];

  Sort[edges]
];

(**
 * Tree2Expr[e]
 *
 * This is a pretty printer of for trees which converts a list
 * of edges into an expression tree. 
 * The nodes will become Heads of the resulting expression. 
 **)
Tree2Expr[e_List] := 
  Module[ {i, a, t, m},

  If[ e === {}, Return[] ];

  m = Max[Flatten[e]];

  (* we implicitly assume that an edge {a,b} is directed from 
     min(a,b) to max(a,b) *)
  1 @@ Table[
    Tree2Expr[Cases[e, {a_, b_} /; a>=i && b>=i]
       /. a_Integer -> a-i+1] 
    /. {a_Integer -> a+i-1, Null -> i},
    {i, 2, m}][[Cases[Sort /@ e, {1, a_} -> a-1]]]
];
