How to generate a random tree?

You can make trees from horses and mazes ;-)

Images for these can be found in documentation for SkeletonTransform and MorphologicalGraph.

Actually, trees are everywhere. Arbitrary expressions have the structure of arbitrary trees. Imagine taking an integral:

Integrate[Sin[(1 - x)/(1 + x)], x]

This will give you a pretty random tree if you apply algorithm from this answer - I am giving only the final line with styles here:

Graph[edges, VertexLabels -> First@labels, 
 ImagePadding -> {{1, 35}, {0, 10}}, GraphLayout -> "RadialDrawing", 
 GraphStyle -> "ThickEdge", DirectedEdges -> False]

Now on a more serious note: There are probably quite a few different ways to do this. In addition to @rm -rf's answer, I mention 6 other possibilities.

1. Random Tree Aggregation

2. Connecting Towns Using Kruskal's Algorithm - Neat, random points in plane construction

3. Tree Form of Recursive Function Evaluation Steps - can give a key to another approach

4. Image processing - see above

5. Random expressions - see above

6. Randomly cut a perfect tree.

You can generate a complete tree of specified number of levels and branches. Here is a tree of 7 levels and 3 branches:

g = CompleteKaryTree[7, 3, GraphStyle -> "LargeNetwork", 
  GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

Then drop a controlled number of edges, and select the largest connected component. Here are a few random samples like that:

rg = Subgraph[g, Sort[ConnectedComponents[
       Graph[RandomSample[#, Round[Length[#] .6]] &@EdgeList[g]]], 
      Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork", 
    GraphLayout -> "RadialDrawing"] & /@ Range[12]

Note that I use "RadialDrawing" layout everywhere, which is good for large trees. Of course you can use the standard one:

AdjacencyGraph[#, GraphStyle -> "LargeNetwork", AspectRatio -> .5] & /@ 
(AdjacencyMatrix /@ rg)

Still, the radial one is excellent for large trees:

g = CompleteKaryTree[10, 4, GraphStyle -> "LargeNetwork", 
   GraphLayout -> "RadialDrawing", VertexShapeFunction -> ({PointSize[0], Point[#]} &)];

Subgraph[g, Sort[ConnectedComponents[
    Graph[RandomSample[#, Round[Length[#] .45]] &@EdgeList[g]]], 
   Length@#1 > Length@#2 &][[1]], GraphStyle -> "LargeNetwork", 
 GraphLayout -> "RadialDrawing", 
 VertexShapeFunction -> ({PointSize[0], Point[#]} &)]

Here is one way of doing it based on an example in TreePlot. We create a function to generate a random set of edges and form a graph as:

vtx[] := Table[i <-> RandomInteger[{0, i - 1}], {i, 1, 50}];
Graph@vtx[]

Generate several:

Table[Graph@vtx[], {12}] ~Partition~ 4 // Grid

The Combinatorica package has a function CodeToLabeledTree[] for generating trees from their corresponding Prüfer codes. Since the old function was adapted for Combinatorica Graph[] objects, as opposed to the built-in Graph[] objects introduced in version 8, some modification of the code in the package is needed:

CodeToLabeledTree[l_List, opts___] := Module[{m = Range[Length[l] + 2], x, i}, 
   TreeGraph[Append[
             Table[x = Min[Complement[m, Drop[l, i - 1]]]; m = Complement[m, {x}]; 
                   UndirectedEdge @@ Sort[{x, l[[i]]}], {i, Length[l]}], 
             UndirectedEdge @@ Sort[m]], opts]] /; Complement[l, Range[Length[l] + 2]] == {}

From this, you can generate a random tree like so:

With[{n = 50}, (* number of vertices *)
 BlockRandom[SeedRandom[42, Method -> "MersenneTwister"]; (* for reproducibility *)
  CodeToLabeledTree[RandomInteger[{1, n}, n - 2], GraphLayout -> "SpringEmbedding"]]]

(The Combinatorica function RandomTree[] is implemented in this way.)