# Labeled Tree from Prüfer Sequence

## Contents

## Algorithm

Given a Prüfer sequence, it is possible to generate a finite labeled tree corresponding to that sequence.

Let $P = \left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$ be a Prüfer sequence. This will be called **the sequence**.

It is assumed the sequence is not empty.

**Step 1**: Draw the $n$ nodes of the tree we are to generate, and label them from $1$ to $n$. This will be called**the tree**.

**Step 2**: Make a list of all the integers $\left({1, 2, \ldots, n}\right)$. This will be called**the list**.

**Step 3**: If there are two numbers left in**the list**, connect them with an edge and then**stop**. Otherwise, continue on to**step 4**.

**Step 4**: Find the smallest number in**the list**which is not in**the sequence**, and also the first number in the**the sequence**. Add an edge to**the tree**connecting the nodes whose labels correspond to those numbers.

**Step 5**: Delete the first of those numbers from**the list**and the second from**the sequence**. This leaves a smaller**list**and a shorter**sequence**. Then return to**step 3**.

The above constitutes an algorithm, for the following reasons:

### Finiteness

For each iteration through the algorithm, **step 5** is executed, which reduces the size of **the list** by $1$.

Therefore, after $n-2$ iterations, at **step 1** there will be $2$ numbers left in **the list**, and the algorithm will stop.

### Definiteness

**Steps 1 and 2**: Trivially definite.

**Step 3**: We are starting with a non-empty Prüfer sequence of length $n-2$, so**the list**must originally contain at least $3$ elements. As the number of elements in**the list**decreases by $1$ each iteration (see**step 5**), eventually there is bound to be just two elements in**the list**.

**Step 4**: As there are more elements in**the list**than there are in**the sequence**, by the Pigeonhole Principle there has to be at least one number in**the list**that is not in**the sequence**.

**Step 5**: Trivially definite.

### Inputs

The input to this algorithm is the Prüfer sequence $\left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$.

### Outputs

The output to this algorithm is the tree $T$.

The fact that $T$ is in fact a tree follows from the fact that:

- Each new edge connects two as yet unconnected parts of $T$, so every edge is a bridge. Therefore there are no cycles in $T$, from Condition for Edge to be Bridge.

So $T$ is a tree from Equivalent Definitions for Finite Tree.

### Effective

Each step of the algorithm is basic enough to be done exactly and in a finite length of time.

## Example

Let the starting Prüfer sequence be $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

**Step 1**:**The sequence**is length $6$, so the tree will have $8$ nodes:

**Step 2**: We generate**the list**: $\left({1, 2, 3, 4, 5, 6, 7, 8}\right)$.

### Iteration 1

**Step 3**: There are $8$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $2$, and the first number in**the sequence**is $1$. We join $1$ and $2$, to obtain this graph:

**Step 5**: We delete $2$ from**the list**to obtain $\left({1, 3, 4, 5, 6, 7, 8}\right)$, and $1$ from the start of**the sequence**to obtain $\left({\mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

### Iteration 2

**Step 3**: There are $7$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $3$, and the first number in**the sequence**is $7$. We join $3$ and $7$, to obtain this graph:

**Step 5**: We delete $3$ from**the list**to obtain $\left({1, 4, 5, 6, 7, 8}\right)$, and $7$ from the start of**the sequence**to obtain $\left({\mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

### Iteration 3

**Step 3**: There are $6$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $4$, and the first number in**the sequence**is $5$. We join $4$ and $5$, to obtain this graph:

**Step 5**: We delete $4$ from**the list**to obtain $\left({1, 5, 6, 7, 8}\right)$, and $5$ from the start of**the sequence**to obtain $\left({\mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

### Iteration 4

**Step 3**: There are $5$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $5$, and the first number in**the sequence**is $7$. We join $5$ and $7$, to obtain this graph:

**Step 5**: We delete $5$ from**the list**to obtain $\left({1, 6, 7, 8}\right)$, and $7$ from the start of**the sequence**to obtain $\left({\mathbf{7}, \mathbf{1}}\right)$.

### Iteration 5

**Step 3**: There are $4$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $6$, and the first number in**the sequence**is $7$. We join $6$ and $7$, to obtain this graph:

**Step 5**: We delete $6$ from**the list**to obtain $\left({1, 7, 8}\right)$, and $7$ from the start of**the sequence**to obtain $\left({\mathbf{1}}\right)$.

### Iteration 6

**Step 3**: There are $3$ elements in**the list**, so we move on to**step 4**.

**Step 4**: The smallest number in**the list**which is not in**the sequence**is $7$, and the first number in**the sequence**is $1$. We join $7$ and $1$, to obtain this graph:

**Step 5**: We delete $7$ from**the list**to obtain $\left({1, 8}\right)$, and $1$ from the start of**the sequence**, which is at this point empty.

### Iteration 7

**Step 3**: There are $2$ elements in**the list**: $\left({1, 8}\right)$, so we join them to obtain this graph:

Then we **stop**.

The algorithm has terminated, and the tree is complete.

Rearranging the positions of the nodes, we can draw it like this:

## Also see

Compare with the example given in Prüfer Sequence from Labeled Tree.

These two results are pulled together in Bijection between Prüfer Sequences and Labeled Trees.