## Trees

All the trees below are *rooted* trees and
ordered in that the order of children (subtrees) from left to right matters.

### 1. Strict Binary Trees

Each node in a *strict binary tree* has either
two child nodes and is called a *Fork* node, or has
zero children and is called a *Leaf* node.
If such a tree has 'f≥0' Fork nodes then it has f+1 Leaf nodes
(proof by induction) so it has 2f+1 nodes in total.

#### 1.1. Encoding Strict Binary Trees

A strict binary tree of 'n' nodes can be encoded succinctly in an
n bit code-word: Perform a prefix traversal of the tree and output
a '0' when first visiting a Fork and a '1' on visiting a Leaf.
It can be seen that the tree can be recovered from the string of bits.
The end of the code-word for the tree is detected upon
seeing one more '1' than '0'
so this is a prefix code for strict binary trees.
It is an efficient code
because pr(Fork) and pr(Leaf) tend to 1/2 as n→∞
and −log_{2}(1/2)=1.

### 2. Binary Trees

Each node in a *binary tree* has two, one or zero child nodes;
in a slight stretch, also call a node with one child a Fork.
(There are variations as to whether or *not* it is significant if
a lone child is on the left or right.)
The parse-tree of an arithmetic expression is an example of a binary tree:
A (node of a) binary operator (+, −, ×, ÷) has
two children, a unary operator (+, − sign) has one child, and
an operand (number, variable) is a Leaf.

#### 2.1. Encoding Binary Trees

A binary tree of 'f' Forks and 'h' Leaves can be encoded in 2f+h bits: Use the method described for strict binary trees but add an extra bit for each Fork to indicate if it has one or two children. This is efficient if the probabilities of Forks having one and two children are equal.

### 3. General Trees

Each node in a *general* or *k-ary tree* can have any
number of child nodes. There is a well-known method of representing such
a tree by a multi-level list:
Each tree node is represented by a list cell which points to its
children (if any) and to its siblings (if any).
Such a list is equivalent to a binary tree; see below.

#### 3.1. Encoding General Trees

A general tree of 'n' nodes can be encoded in 2n bits if n is
common knowledge and an 2n+1 bits otherwise:
Perform a prefix traversal of the tree and output a '0' when going *Down*
an edge and a '1' when going back *Up* an edge.
If n is not common knowledge then we are unable to detect the end
of the code-word but if an extra '1' (Up) is appended we can,
giving a prefix code for general trees.

### 4. How Many?

The numbers of
(i) strings of 'b' pairs of matched
brackets '(' and ')'
also known as parentheses,
(ii) general trees of b+1 nodes, and
(iii) strict binary trees of b Forks,
are all the same and equal to the b^{th} Catalan number^{*},
e.g., b=3, C_{b}=5:

((())) (()()) (())() ()(()) ()()() 0001111 0010111 0011011 0100111 0101011

Starting with general trees (R=root)

R R R R R | | / \ / \ /|\ . . . . . . . . . | / \ | | . . . . . | . DDDUUU DDUDUU DDUUDU DUDDUU DUDUDU 0001111 0010111 0011011 0100111 0101011

Convert to multi-level lists

R R R R R | | | | | . . .--. .--. .--.--. | | | | . .--. . . | .

Rotate clockwise slightly and add leaves (not shown) to vacant pointers in Forks giving strict binary trees;

R R R R R / / / / / F F F F F / / / \ \ \ F F F F F F / \ / \ F F F F

Finally, remove (uninteresting) root nodes still leaving strict binary trees (leaves not shown)

F F F F F / / / \ \ \ F F F F F F / \ / \ F F F F FFFLLLL FFLFLLL FFLLFLL FLFFLLL FLFLFLL 0001111 0010111 0011011 0100111 0101011

The tree encodings are exploited in certain universal codes [AKS21] for large integers used in data-compression and A.I..

### References

- [AKS21] Lloyd Allison, Arun S. Konagurthu & Daniel F. Schmidt, 'On Universal Codes for Integers: Wallace Tree, Elias Omega and Beyond', Data Compression Conference (DCC), pp.313-322, doi:10.1109/DCC50243.2021.00039, 22-26 March 2021.

And other publications.

^{*}Catalan numbers, C_{n}, n≥0:
1, 1, 2, 5, 14, 42, ...,
C_{0}=1,
C_{n+1}=∑_{i=0..n}C_{i}C_{n-i}