Tree code

An arbitrary tree (binary or not binary, directed (= rooted) or undirected) can be presented by a sequence of node numbers (tree code). If a tree contains n nodes then the code contains n – 2 node numbers.

Algorithm for tree coding (assuming that n nodes are marked with numbers 1, 2, …, n):

1. Find a leaf with a minimal number and delete it from the tree together with its adjacent edge. (In the picture, deleting an edge is denoted by a short solid line.) Enter the number of the node adjacent to the deleted one into a new last position of the code.

2. Repeat the step 1 (n – 2) times (until 2 nodes and 1 connecting edge are left in tree).

Ex.:

(2, 1, 2, 1, 2) ç code

Restoring tree by its code:

List of node numbers è 1, 2, 3, 4, 5, 6, 7

Tree code è 2, 1, 2, 1, 2

Node numbers 3, 4, 5, 6, 7 from the list are absent in the code. So they are leaves in the original tree.

Algorithm:

1. Connect the smallest number in the remaining list with the first current number in the code. Delete the connected node numbers from the list and the code.

2. Repeat step 1 until all code numbers are connected with list numbers.

3. Connect the remaining two numbers of the list.

Ex: list: 1, 2, 3, 4, 5, 6, 7 1, 2, 4, 5, 6, 7 1, 2, 5, 6, 7 1, 2, 6, 7 1, 2, 7 2, 7

code: 2, 1, 2, 1, 2 1, 2, 1, 2 2, 1, 2 1, 2 2

Now we have to connect the lines of each step in one picture.