# Random Tree generator using Prufer Sequence in C++

First, we need to understand the question and what is asked here.

We are here provided with an integer N first.

The task we have in our hands here is to create a Prufer Sequence,  i.e we have to generate a random labelled tree of N node with `(N-1)` edges.

• Condition: We can’t form a full cycle.
• The output which we will receive from the code written below may differ from the examples we take here.

## Examples

Example 1)

```Input:

N=3

Output:

1 2

1 3```

Here as we can see a labelled tree: ```Example 2:

Input :

N=5

Output:

1 5

1 4

3 2

4 3```

## What is Prufer Sequence

Prufer sequence is derived from mathematics which can also be called Prufer Code or Prufer numbers of a labelled tree is an association which is observed in trees.

The sequence of the trees here has n vertices, also it has a length of n-2, and we may use a general iterative approach to reach the solution.

If we are provided with N nodes and also the length being `(N-2)`, then each position in the Prufer sequence can have N Possible Values.

So, The number of possible labelled trees in a Prufer Sequence with N Nodes is, `N^(N-2)`.

## How Trees are Generated using Prufer Sequence

The following steps are done in generating random trees with N Nodes:

`K={k1,k2,k3,.......,k(n-2)}`, where each element ki belongs in `{1,2,3,......N}`

Now we take an example to have a clear understanding of what is being said here:

For Example:

Nodes : 3

Now, the length should be `(N-2)`, but in this case, we can only have `{1,2,3}`

Therefore , the sequence we can have here : `{{1},{2},{3}}`

#### Possible Trees: Now we look at the implementation:

```#include<bits/stdc++.h>
using namespace std;
void printTreeEdges(int prufer[], int m)
{
int vertices = m + 2;
int vertex_set[vertices];

for (int i = 0; i < vertices; i++)
vertex_set[i] = 0;

for (int i = 0; i < vertices - 2; i++)
vertex_set[prufer[i] - 1] += 1;

cout<<("\nThe edge set E(G) is:\n");

int j = 0;

for (int i = 0; i < vertices - 2; i++)
{
for (j = 0; j < vertices; j++)
{

if (vertex_set[j] == 0)
{

vertex_set[j] = -1;
cout<<"(" << (j + 1) << ", "
<< prufer[i] << ") ";

vertex_set[prufer[i] - 1]--;

break;
}
}
}

j = 0;

for (int i = 0; i < vertices; i++)
{
if (vertex_set[i] == 0 && j == 0)
{

cout << "(" << (i + 1) << ", ";
j++;
}
else if (vertex_set[i] == 0 && j == 1)
cout << (i + 1) << ")\n";
}
}

int ran(int l, int r)
{
return l + (rand() % (r - l + 1));
}

void generateRandomTree(int n)
{

int length = n - 2;
int arr[length];

for (int i = 0; i < length; i++)
{
arr[i] = ran(0, pow(2, length + 1)) + 1;
}
printTreeEdges(arr, length);
}

int main()
{
srand(time(0));
int n = 7;
generateRandomTree(n);

return 0;
}```
```Input:

N=7

Output:

The edge set E(G) is:

(1, 26) (2, 46) (3, 38) (4, 24) (5, 32) (6, 7)
```