Ordered Trees

1. Definition

An ordered tree is a tree with a chosen root vertex in which the children of each vertex are ordered.

An ordered tree $T$ is left-heavy if, for each vertex $v$ of $T$, its children are ordered from left to right by non-increasing sizes of their subtrees. Similary, an ordered tree is right-heavy if, for each vertex $v$ of $T$, its children are ordered from right to left by non-increasing sizes of their subtrees.

The size of the tree is the number of nodes.

2. Examples

Ordered trees of size 1: (the root is on top and the leafs are not represented)

Ordered trees of size 2:

Ordered trees of size 3:

Ordered trees of size 4:

3. Properties

Ordered trees retain all properties of regular tree with the only restriction being that all children of every vertex of an ordered tree must be ordered. If each vertex is labeled by distinct and nonnegative integers, then the ordered tree is called an ordered labeled tree. [Seo15].

Given an ordered tree of size $n+1$, the amount of ways the tree can be structured is $\operatorname{Cat}_n = \frac{1}{n+1}\binom{2n}{n}$. That is, with an ordered tree of size 3, we would have $\frac{1}{3}\binom{4}{2}$ = 2 different structures that represent the tree.

4. Remarks

The terminal Wiener index of a tree is defined as the sum of distances between all pairs of pendent vertices of trees. [Che15]. This has arisen in the study of phylogenetic tree reconstruction and the neighborhood of trees.

5. Statistics

We have the following 19 statistics on Ordered trees in the database:

The number of subtrees.
The number of linear extensions of the tree.
The depth of an ordered tree.
The depth minus 1 of an ordered tree.
The number of leaves of an ordered tree.
The number of internal nodes of an ordered tree.
The maximum number of child nodes in a tree.
The Strahler number of a rooted tree.
The path length of an ordered tree.
The tree factorial of an ordered tree.
The number of ordered trees with the same underlying unordered tree.
The size of the automorphism group of the rooted tree underlying the ordered tree....
The number of inequivalent increasing trees of an ordered tree.
The size of the automorphism group of the ordered tree.
The number of distinct subtrees of an ordered tree.
The number of 1-protected nodes of a rooted tree.
The number of 2-protected nodes of a rooted tree.
The pruning number of an ordered tree.
The protection number of an ordered tree.

6. Maps

We have the following 11 maps in the database:

to complete tree
to ordered tree: left child = left brother
to ordered tree: right child = right brother
to ordered tree
to graph
to poset
left-right symmetry
to binary tree: left brother = left child
to binary tree: right brother = right child
to Dyck path
Zeilberger's Strahler bijection

7. References

[Che15]   Y. Chen, The Terminal Wiener Index of Trees with Diameter or Maximum Degree, 2015, http://arxiv.org/abs/1510.03126.

[Seo15]   S. Seo, A Refinemene for Ordered Labeled Tree, 2015, http://arxiv.org/abs/1207.3291.

8. Sage examples


CategoryCombinatorialCollection