# Prufer Code to Tree Creation in C++

In this article, I am going to generate a Tree from a Prufer Code using C++ with example. I hope you will enjoy this tutorial.

At first, we have to know the definition of prufer code.

Prufer Code: Introduction:

Every labeled tree having N vertices can be uniquely represented by an array having N-2 entries and vice versa. This array is the corresponding Prufer Code of that Tree.

Now let’s learn how we can get a tree from a prufer code by an algorithm.

## Prufer Code to Tree: Algorithm steps

Step 1: First take an input of the code from the user of length n. Create a graph with n+2 vertices.

Step 2: Remove the first array element.

step 3: We have to find the minimum value which is not present in that array. Connect these two vertices with an edge.

Step 4: Add that value at the end of the remaining array.

Step 5: Repeat steps 2 to 5 until only 2 vertices left to connect.

Following is a simple example to understand the above algorithm:

Given Prufer Code is {4, 2, 3, 4}.

Step 1: Given code has four vertices, therefore the tree will have 6 vertices.

Step 2: The first number in the Prufer Code is 4 and the minimum number not present in code is 1. So, connect 4 to 1.

`1----4`

Remove 4 from the array and add 1 at the back of the Code: {2, 3, 4, 1}.

Step 3: Next select 2 and the minimum number not present in Code is 5.

`1----4       2----5`

After this step, the code is: {3, 4, 1, 5}.

Step 4: Next select 3 and connect with the corresponding vertex with least degree 2.

`1----4      3----2----5`

After this step, the code is: {4, 1, 5, 2}.

Step 5: Next select 4 and connect with the minimum number not present in code is 3.So, connect 4 to 3

`1----4----3----2----5`

After this step, the code is: {1, 5, 2, 3}.

Step 6: At last out of six vertices two vertices are left, so connect them. Visit the below link for the final answer.

```1----4----3----2----5

|

6```

For more example visit this pdf

This is the Tree.

## C++ program: Prufer Code to Tree Creation

Below is the given C++ code

```#include <bits/stdc++.h>
using namespace std;
//Print the set of the tree represented by given Prufer code
void pruferCodeToTree(int pf[],int n)
{
int ver=n+2;
int v_set[ver];
// Initialize the array
for (int i=0;i<ver;i++){
v_set[i] = 0;
}
// Number of occurrences of vertices in the given code
for (int i=0;i<ver-2;i++)
v_set[pf[i]-1]+=1;
int j=0;
for (int i=0;i<ver-2;i++){
for (j=0;j<ver;j++){
// If j+1 is not present in prufer set
if (v_set[j]==0){
// Remove from Prufer set and print pair.
v_set[j]=-1;
cout<<"("<<(j+1)<<","
<<pf[i]<<")  ";
v_set[pf[i]-1]--;
break;
}
}
}
//last element
j=0;
for (int i=0;i<ver;i++){
if (v_set[i]==0&&j==0){
cout<<"("<<(i+1)<<",";
j++;
}
else if(v_set[i]==0&&j==1)
cout <<(i+1)<<")\n";
}
}
//main function

int main()
{
int n,prufer[n],i;
cin>>n;
for(i=0;i<n;i++){
cin>>prufer[i];
}
pruferCodeToTree(prufer,n);
return 0;
}```

Output:

```4
4 2 3 4
(1,4)  (5,2)  (2,3)  (3,4)  (4,6)```