Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Is it possible to generate a random tree without explicitly constructing a random adjacency matrix that satisfies tree properties? How about a random directed tree?

Edit: incredible answer by Vitaliy! What I wanted was somewhat simpler and rm -rf's answer largely pointed me in the right direction. One thing to note is that the TreeGraph functions (new in version 8), while easy to use, seem to be lacking some functionality compared to the older TreePlot family of functions. In particular, I wanted to make sure that the root of my tree is displayed at the top, and I could not find a way to do it with TreeGraph -- please correct me if I missed something! Here is the illustration (notice how TreeGraph puts node 1 at the top):

Block[{edges, p1, p2},
 edges = Table[DirectedEdge[RandomInteger[{0, i - 1}], i], {i, 1, 8}];
 p1 = TreeGraph[edges, GraphStyle -> "DiagramBlack"] ;
 p2 = TreePlot[edges /. {DirectedEdge -> Rule}, Top, 0, 
   DirectedEdges -> True, 
   VertexRenderingFunction -> ({White, EdgeForm[Black], Disk[#, .1], 
       Black, Text[#2, #1]} &)];
 GraphicsGrid[{{p1, p2}}, ImageSize -> 800]

tree visualization

share|improve this question
Re: your edit, you can try using LayeredGraphPlot – R. M. Oct 17 '12 at 21:10
up vote 18 down vote accepted

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}];

Generate several:

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

share|improve this answer
The doc page for TreeGraph[] also gives some code for generating a random tree. – J. M. Oct 6 '12 at 9:42

You can make trees from horses and mazes ;-)

maze to tree

horse to tree

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]

integral of Sin[(1 - x)/(1 + 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]

tree from expression

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[#]} &)]

k-ary tree with 7 levels and 3 branches

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]

random subgraphs of k-ary tree

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)

adjacency graph

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[#]} &)]

subgraph of k-ary tree

share|improve this answer
In version 10 or later,we shoul add a option GraphLayout-> "LayeredEmbedding".Suggestion you add in your answer to help read. – yode Apr 4 at 20:39
@Vitaliy my trees are different, I have a Mathematica 10.4 , How to do this like your trees? – vito Jun 22 at 22:46

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}, 
             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"]]]

random graph from Prüfer code

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

share|improve this answer

Similar to the one in the documentation. I just made it into a function so that you can specify the number of vertices.

randomTree[n_, opts___] := 
    Graph[Range@n, # + 1 <-> RandomInteger[{1, #}] & /@ Range[n - 1], opts]
share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.