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.


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


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.




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++) 
    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.               
                     <<pf[i]<<")  "; 
    //last element
    for (int i=0;i<ver;i++){ 
        if (v_set[i]==0&&j==0){ 
        else if(v_set[i]==0&&j==1) 
            cout <<(i+1)<<")\n"; 
//main function

int main() 
  int n,prufer[n],i;
    return 0; 



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

Leave a Reply

Your email address will not be published. Required fields are marked *