Develop an algorithm for reconstructing a tree from a given

Develop an algorithm for reconstructing a tree from a given Prüfer Code: a₁,a₂, ... , a_n-2

Solution

Algorithm: Pr¨ufer’s code

Input: A tree T with vertex set S N where |S| 2.

Output: A sequence f(T) = (a1 , a2, . . . , a_|S|2 ) S ^|S|2

let T₁ = T

for each i = 1 to |S| 2 do

let v be the leaf of T_i with smallest label

set ai to be the unique neighbour of v in T

construct T_i+1 from T_i by removing the vertex v and the edge {v, a_i}

end for