Code length
|P| = n − 2
Two vertices remain after all recorded leaf removals.
Prüfer Code Encoder and Tree Decoder
Choose a conversion
Use consecutive labels from 1 through n.
Keyboard shortcut: Ctrl+Enter or ⌘+Enter converts the current input.
Private by design: the tree, code, diagram, and downloads stay on this device. This tool does not upload or save your input.
Advertisement
What is a Prüfer code?
A Prüfer code (or Prüfer sequence) is a compact representation of a labeled tree. For a tree whose vertex labels are {1,2,…,n}, its code contains exactly n − 2 labels. Repeated labels are allowed, and a label appears exactly degree(v) − 1 times.
Vertex degree
deg(v) = 1 + countP(v)
Every occurrence of a label adds one to that vertex’s degree.
Number of codes
nⁿ⁻²
There are n choices at each of n − 2 positions, matching Cayley’s labeled-tree count.
How encoding and decoding work
Encode a tree
Find the remaining leaf with the smallest label, record its only neighbor, and remove the leaf and its incident edge. Repeat until only two vertices remain.
Decode a code
Set each degree to one, then add one for each appearance in the code. For each code value, connect it to the smallest current degree-one vertex and update both degrees. Connect the final two leaves.
Why the smallest leaf?
Choosing the smallest label makes the procedure deterministic. Without a fixed choice rule, one tree could produce different sequences.
Why the correspondence is unique
The decoder exactly reverses the encoder’s leaf removals. A fixed label set therefore gives a one-to-one correspondence between codes and labeled trees.
Prüfer encoding example
Take the tree with edges 1–2, 1–3, 3–4, 3–5, 5–6. Always remove the smallest labeled leaf:
- Leaf 2 is adjacent to 1, so record 1.
- Vertex 1 is now a leaf adjacent to 3, so record 3.
- Leaf 4 is adjacent to 3, so record another 3.
- Vertex 3 is now the smallest leaf and is adjacent to 5, so record 5.
Vertices 5 and 6 remain, so the final code is (1, 3, 3, 5). Decoding that sequence reconstructs the same five edges.
Input rules, assumptions, and limits
Labels are base-10 positive integers in the canonical set 1,2,…,n. Encoding accepts 2 ≤ n ≤ 500 and requires exactly n − 1 distinct, non-loop edges forming one connected acyclic graph. Each edge must be on its own line. Decoding accepts at most 498 code values, giving at most 500 vertices; every code value must lie from 1 through n = |P| + 2.
The empty sequence is deliberately accepted and decodes to the two-vertex tree with edge 1–2. Leading zeros are accepted and normalized. Signed values, decimals, scientific notation, repeated edges, self-loops, cycles, disconnected edge sets, and labels outside the inferred range are rejected.
For readability, the SVG preview is shown for at most 40 vertices. The complete edge list, Prüfer code, steps, copy action, and CSV export remain available throughout the 500-vertex limit.
Historical note: Heinz Prüfer introduced this encoding in his 1918 paper Neuer Beweis eines Satzes über Permutationen. The deterministic algorithm used here follows the standard smallest-labeled-leaf convention.
Calculation note: encoding, decoding, round trips, the empty code, stars, paths, repeated code values, cycles, duplicate edges, disconnected inputs, range errors, and maximum sizes checked by the Starlight Tools editorial team. Last reviewed: .
Prüfer code FAQ
What is a Prüfer code?
It is a sequence of n − 2 vertex labels that uniquely identifies a labeled tree on the fixed labels 1 through n.
How do I encode a tree as a Prüfer sequence?
Repeatedly remove the leaf with the smallest label and append its neighbor’s label to the sequence. Stop when two vertices remain.
How is a Prüfer code decoded?
Use the code counts to initialize degrees. Repeatedly connect the smallest degree-one vertex to the next code label, reduce both degrees, and finally connect the two remaining leaves.
Can two different labeled trees have the same code?
No. Prüfer coding is a bijection for a fixed label set: encoding produces one deterministic sequence, and decoding it reconstructs the original labeled tree.
Is an empty Prüfer code valid?
Yes. Its length is zero, so n = 0 + 2 = 2. The represented tree contains the single edge 1–2.
What does the number of occurrences of a label mean?
A vertex label appears exactly one fewer time than that vertex’s degree. For example, a label appearing three times belongs to a degree-four vertex.
Why did the tree input fail validation?
A tree on n vertices must contain exactly n − 1 distinct non-loop edges, use only labels 1 through n, contain no cycle, and connect every vertex.
Does this tool upload my tree or code?
No. Conversion, validation, diagram generation, copying, and CSV creation run in your browser, without storing or transmitting the input.