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

Information on Rooted Plane Trees

A plane tree is a (free) tree that has been embedded in the plane. If some node is distinguished as the root, then such trees are called rooted plane trees. A rooted plane tree is a rooted tree with a left to right ordering specified for the children of each non-root vertex. However, what distinguishes these trees from ordered trees is that the children of the root are determined only up to a circular rotation.

Below we show the 10 non-isomorphic rooted plane trees with 5 nodes. Roots are shown in blue. Notice that trees (3) and (4) are equivalent as rooted trees and that the mirror image of tree (5) is not in the list since it could be obtained from (5) by rotating its subtrees about the root.

Alternatively, a rooted plane tree can be thought of as an equivalence class of ordered trees, where two ordered trees are considered equivalent if one can be obtained from the other by a circular rotation of subtrees about the root. This interpretation forms the basis for our representation of rooted plane trees which is explained next.



One 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.

Another 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.



The two trees shown above are the same when regarded as unlabelled rooted plane trees, since one may be obtained from the other by rotating subtrees about the root. Among all ordered trees that are equivalent we choose the one whose level sequence is lexicographically smallest (i.e., least when regarded as a number) and call it canonic. By generating canonic ordered trees, we generate all rooted plane trees. The second tree illustrated is canonic (the one with level sequence 0112334212). The list of all rooted plane trees with 5 nodes shown at the top of this page shows the canonic tree from each equivalence class. From left-to-right their level sequences are 01234, 01233, 01232, 01223, 01123, 01222, 01122, 01212, 01112, 01111.

If r(n) denotes the number of non-isomorphic rooted plane trees with n nodes.

r(n+1)   =  
 1
2n
 
__
\
/   
d | n
Ø(n/d) (
2d
d
)
 

For n = 1,2,...,15 the number of rooted plane trees, r(n) is 1, 1, 2, 4, 10, 26, 80, 246, 810, 2704, 9252, 32066, 112720, 400024, 1432860. This is sequence A003239(M1222) in Neil J. Sloane's database of integer sequences.

Correspondence with necklaces

This sequence also represents the number of necklaces composed of n-1 white beads and n-1 black beads. To get the correspondence, start at root, walk around the outside of tree (i.e., as in a depth-first search), using one color if following an edge away from the root, and the other color if following and edge towards the root. If you wish to generate these necklaces then the necklace section of COS may be used, with 2d = n and k = 2 in the input.

COS options

In COS the user can output the level sequence (standard representation) and/or the parent array (alternate representation). The algorithm used is from Joe Sawada, Generating rooted and free plane trees, 2002, submitted to ACM Transactions on Algorithms. The sequences are produced in increasing lexicographic order.


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 11:00:31 PDT.
There have been 6195 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.