Sometimes you stumble over some cool things you *really* wish you could use
right away – like the Prüfer
sequence. The Prüfer
sequence is a way of uniquely representing trees of *n* nodes with a sequence of
*n-2* node labels. The tree shown below, which has six nodes can thus be
represented by a string of four labels, namely “**3334**”.

To come up with the Prüfer sequence for the tree you first have to come up with
an order for the node labels. For the tree above this is simply *0, 1, 2, …*.
You then start with the “smallest” label, remove it and add the node it is
connected to to the sequence. Here, that would be to remove node *0* and add *3*
to the sequence. The next nodes would be node *1* and *2*, which are also
connected to node *3*, yielding the sequence “**333**” after three steps. You
would then remove node *3* and add *4* to the sequence. When only two nodes are
left you stop. The final result is thus “**3334**”.

To go from a Prüfer sequence to a tree you first find the degree of each node,
this is simply done by counting its occurrences in the sequence and add one,
meaning that node *0* has degree 0+1=1, while node *3* has degree 3+1=4. You can
the do the reverse of the encoding process: for each node in the sequence, add
an edge from it to the first node with degree 1 and reduce both nodes’ degree.
This is done until you have only two nodes left which should be connected.

Python code for decoding a Prüfer sequence into an array of node pairs (connection):

```
def prufer_to_tree(a):
= []
tree = range(0, len(a)+2)
T
# the degree of each node is how many times it appears
# in the sequence
= [1]*len(T)
deg for i in a: deg[i] += 1
# for each node label i in a, find the first node j with degree 1 and add
# the edge (j, i) to the tree
for i in a:
for j in T:
if deg[j] == 1:
tree.append((i,j))# decrement the degrees of i and j
-= 1
deg[i] -= 1
deg[j] break
= [x for x in T if deg[x] == 1]
last 0],last[1]))
tree.append((last[
return tree
```