# How can I generate random (not necessairly binary) tree?

I'm learning data structers and trying to write program, which would generate me a tree (not necessarily binary one) that contains n vertices. So far I tried Prufer sequence and it works for me well - it's very interesting solution of a problem. I found paper with Fast Random Tree Generating Algorithm (page 881-882).

Actually, I don't really care about speed of generation, but this method should be faster than generating tree from Prufer sequence. I wrote code to generate it, and I am not sure if it works correctly. Something is wrong with my code, or with the method presented in the above paper. Below I show what I produced. Code is written in Python3. Note that I changed indexing as Python is 0-indexed.

``````import random

def fast_random_tree(n):
"""
"""
I = list(range(n))  # Initial vector of node numbers
root = random.randint(0, n - 2)  # choosing root
I[root], I[-1] = I[-1], I[root]  # replacing with last value
edges = [None for _ in range(n - 1)]
for m in range(n - 1):
t = random.randint(0, m)  # new node
s = random.randint(m + 1, n - 1)
edges[m] = (I[t], I[s])  # adding edgde
I[t], I[n - m - 1] = I[n - m - 1], I[t]  # replaceing from n-m+1 to n - nodes that are in a tree already

return edges

if __name__ == '__main__':
edges = fast_random_tree(5)
print(edges)
``````

Sometimes I receive set of edges that does not create tree, because it contains cycles or graph is not fully connected. Example:

``````>>> print(fast_random_tree(5))
[(0, 4), (0, 3), (1, 2), (2, 1)]

0      1
/ \     |
4   3    2
``````

which is obviously not a tree. What also concerns me is that root is choosen randomly and moved to last position in array, but it can never be connected to some other vertice.

Do I forget about something or just this algorithm does not work? If you know other algorithms to generate a random tree I would love to read about it. Thanks for any help in advance!