8.4 How to Store Trees 15105216374FIGURE 8.5. A tree reconstructed from its Pr ̈ufer codeHow does the first row start? Remember that this is the node that we
delete in the first step; by the rule of constructing the Pr ̈ufer code, this is
the node with degree 1 with smallest label. Could this node be node 1? No,
because then we would have to delete it in the first step, and it could no
longer occur, but it does. By the same token, no number occurring in the
second row could be a leaf of the tree at the beginning. This rules out 2,3,
and 4.
What about 5? It does not occur in the second row; does this mean that
it is a leaf of the original tree? The answer is yes; otherwise, 5 would have
been the father of some other node, and it would have been written in
the second row when this other node was deleted. Thus 5 was a leaf with
smallest label, and the first row of the extended Pr ̈ufer code must start
with 5.
Let’s try to figure out the next entry in the first row, which is, as we
know, the leaf with smallest label of the tree after 5 was deleted. The node
1 is still ruled out, since it occurs later in the second row ; but 2 does not
occur again, which means (by the same argument as before) that 2 was the
leaf with smallest label after 5 was deleted. Thus the second entry in the
first row is 2.
Similarly, the third entry must be 4, since all the smaller numbers either
occur later or have been used already. Continuing in a similar fashion, we
get that the full array must have been
5246731
2403310This corresponds to the tree in Figure 8.5
Proof.[of Lemma 8.4.1] The considerations above are completely general,
and can be summed up as follows:
Each entry in the first row of the extended Pr ̈ufer code is the
smallest integer that does not occur in the first row before it,
nor in the second row below or after it.