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.