Application of Prufer Code: Random Tree Generation, Cayley’s Formula and Building Tree from Degree Count
On the last post (Prufer Code: Linear Representation of a Labeled Tree), we discussed how to convert a labeled tree into Prufer Code and vice versa. On this post, we will look into some of its applications in problem-solving.
Generating Random Tree
This one is the simplest. Though problem-solving may not require generating random trees, problem setting might. In order to generate a random tree with N nodes, all we need to do is generate a Prufer Code of length N-2 with each element being in the range of 1 to N. Next, we just convert the Prufer Code into a tree.
The randomness of the tree depends on the randomness of the sequence generated. Using rand()
function is not good since it’s not truly random. How we can generate a random sequence requires a blog post of its own. Maybe I will write a post on it in near future.