# 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)

## Leave a Reply