# How can I randomly generate trees?

I want to randomly generate trees, i.e. undirected acyclic graphs with a single root, making sure that all possible trees with a fixed number of nodes n are equally likely.

-

Knuth says to look at it as generating all nested parentheses in lexicographic order.

Look here for the details

-
I think that link should just be www-cs-faculty.stanford.edu/~uno/fasc4a.ps. Somehow you got the Google tracking page in there when you copied the link. –  Ben Alpert Jul 25 '10 at 15:55
Fixed, thanks Ben –  Jonathan Fischoff Jul 25 '10 at 19:28
And now there's no http://, which you need to make it a link. (I had it in my comment but it was stripped out.) –  Ben Alpert Jul 25 '10 at 19:38
Eric Lippert has been doing a series on something similar - blogs.msdn.com/b/ericlippert/archive/2010/04/22/…, which might be an interesting read. –  dsolimano Jul 26 '10 at 3:00
I only read the first few sentences but its interesting that binary tree's are Catalan numbers, I knew triangulations were, but either learned that and forgot or never knew. –  Jonathan Fischoff Jul 26 '10 at 4:36

To generate a random tree you can use the following algorithm, where dst and src are two stacks:

dst := random permutation of all nodes;
src := empty stack
src.push(dst.pop()); % picks the root
while (!dst.empty()) {
a := random element from src;
b := dst.pop();