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)