[Information Index] [Generation Index] [COS homepage]

Information on Rooted Trees

A rooted tree may be defined as a free tree in which some node has been distinguished as the root. Above we show a list of all 9 rooted trees on 5 vertices. Roots are shown in blue.

A rooted tree may be regarded as an equivalence class of ordered trees. Two ordered trees are equivalent if one may be transformed into the other by re-ordering subtrees. In the figure above the number of ordered trees in the equivalence class of each rooted tree is 1, 1, 2, 2, 1, 2, 1, 3, 1, respectively. The sum of these numbers is 14, the 5th Catalan number and the number of ordered trees on 5 nodes.

One natural way of encoding an ordered tree is to record the parent of each node in preorder. In the figure on the left each node points to its parent. Taking 0 to be the parent of the root, the sequence obtained is 0121156685. This is called the parent array.

Another way of encoding an ordered tree is to record the level (distance from the root) at which its nodes occur in preorder. In the tree shown on the right the numbers give a preorder labelling and by recording the level number of those nodes we obtain the sequence 0121123342. This is called the level sequence.

The two trees shown above are the same when regarded as unlabelled rooted trees, since one may be obtained from the other by reordering subtrees. Among all ordered trees that are equivalent we choose the one whose parent array is lexicographically largest (i.e., biggest when regarded as a number) and call it canonic. By generating canonic ordered trees, we generate all rooted trees. The second tree illustrated is canonic (the one with parent array 0123432181). Intuitively, we transform an ordered tree into a canonic tree by recursively pushing subtrees with greater height to the left. The list of all trees with 5 nodes shown at the top of this page shows the canonic tree from each equivalence class.

For n = 1,2,3,...,15 the number of rooted trees is 1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, 87811. This is sequence A000081(M1180) in Neil J. Sloane's database of integer sequences.

Binary Rooted Trees

An important subclass of the rooted trees are the those in which every node has either two children or is a leaf (has no children). These trees are output by the program by setting m = 2 (giving the list shown above), and then by adding n+1 leaves to the resulting trees, as shown below.

The number of binary rooted trees with n = 1,2,3,...,15 internal nodes is 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, respectively. This is sequence A001190(M0790) in Neil J. Sloane's database of integer sequences.

Rooted trees where each node has at most 3 children are sometimes called quartic planted trees. For n = 1,2,3,...,15 internal nodes, there are 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241, 48865 of them, respectively. This is sequence A000598(M1146) in Neil J. Sloane's database of integer sequences.

Rooted trees where each node has at most 4 children are counted for n = 1,2,3,...,20 nodes, by the numbers 1, 1, 2, 4, 9, 19, 45, 106, 260, 643, 1624, 4138, 10683, 27790, 72917, 192548, 511624, 1366424, 3666930, 9881527, respectively. This is sequence A036718 in Neil J. Sloane's database of integer sequences.

The asymptotic number of binary rooted trees has been studied by Otter and others. You may click here for further information.

Counts of rooted trees classified by height

n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1
2 1
3 1 1
4 1 2 1
5 1 4 3 1
6 1 6 8 4 1
7 1 10 18 13 5 1
8 1 14 38 36 19 6 1
9 1 21 76 93 61 26 7 1
10 1 29 147 225 180 94 34 8 1
11 1 41 277 528 498 308 136 43 9 1
12 1 55 509 1198 1323 941 487 188 53 10 1
13 1 76 924 2666 3405 2744 1615 728 251 64 11 1
14 1 100 1648 5815 8557 7722 5079 2593 1043 326 76 12 1
15 1 134 2912 12517 21103 21166 15349 8706 3961 1445 414 89 13 1

The sum of the first two columns is the number of numerical partitions of n+1. The sum of the first three columns is Sloane's A001383(M1107). The sum of the first four columns is Sloane's A001384(M1172).

COS options

In COS the user can output the parent array (standard representation) or the level sequence (alternate representation). An upper bound on the number of children of a node can be specified (as m). Upper and lower bounds on the height can also be specified (as lb and ub). The algorithm used in COS is from Gang Li and Frank Ruskey, The Advantages of Forward Thinking in Generating Rooted and Free Trees, 10th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (1999) S939-940.

Programs available:
[Information Index] [Generation Index] [COS homepage]
Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Tuesday, 24-May-2011 10:56:18 PDT.
There have been 11460 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.