Arthur Cayley first proved that there are \(n^{n-2}\) labeled trees on \(n\) vertices, and in another proof of the same theorem, Heinz Prüfer showed a bijection between trees on \(n\) vertices and \((n-2)\)-tuples of integers from 1 to \(n – 2\), called Prüfer codes. The proof provides an algorithm that allows us to construct an arbitrary labeled tree from its code.

The algorithm proceeds as follows:

1. Initialise an array of node degrees for the nodes, which are numbered from 1 to \(n + 2\)
2. For each occurrence of a node number in the code, increment its degree
3. Add 1 to all degrees
4. For each occurrence of a node number in the code:
   1. Find the lowest-numbered node with degree 1
   2. Create an edge between that node and the node in the code
   3. Decrement the degrees of both nodes by 1
5. There are now 2 nodes left with degree 1, so join them with an edge to complete the tree

Below is an implementation of the algorithm in C. The function prufer_tree() takes a code in the form of an array of unsigned integers and its length, and returns the tree as an array of edges.

#include <stdlib.h>

typedef struct {
    unsigned int first;
    unsigned int second;
} edge;

edge *prufer_tree(const unsigned int *code, size_t len)
{
    unsigned int i, j, e = 0;
    const unsigned int n = len + 2; /* Nodes */
    edge *tree = malloc((n - 1) * sizeof(edge));
    unsigned int *degrees = calloc(n + 1, sizeof(unsigned int)); /* 1-based */
    if (tree == NULL || degrees == NULL) {
        free(tree);
        free(degrees);
        return NULL;
    }
    /* Set the degrees from the occurrences in the code */
    for (i = 0; i < len; i++) {
        degrees[ code[i]]++;
    }
    /* Add 1 to them all */
    for (i = 1; i <= n; i++) {
        degrees[i]++;
    }
    /* Add edges to nodes in the code */
    for (i = 0; i < len; i++) {
        /* Find the lowest-numbered node with degree 1 */
        for (j = 1; degrees[j] != 1; j++);
        /* Add the edge */
        tree[e].first = j;
        tree[e].second = code[i];
        degrees[j]--;
        degrees[ code[i]]--;
        e++;
    }
    /* Find the last 2 degree-1 nodes */
    for (i = 1; degrees[i] != 1; i++);
    for (j = i + 1; degrees[j] != 1; j++);
    /* Add the last edge */
    tree[e].first = i;
    tree[e].second = j;
    free(degrees);

    return tree;
}

Here is an example program that constructs the tree in the image at the top:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned int code[] = {1, 1, 1, 1, 6, 5};
    const size_t len = sizeof(code) / sizeof(unsigned int);
    const unsigned int n = len + 1; /* Edges */
    edge *tree = prufer_tree(code, len);
    unsigned int e;
    for (e = 0; e < n; e++) {
        printf("(%u, %u)\n", tree[e].first, tree[e].second);
    }
    free(tree);
    return 0;
}

The output:

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