edit this page

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 22 statistics in the database:

St000084
Ordered trees ⟶ ℤ
The number of subtrees.
St000085
Ordered trees ⟶ ℤ
The number of linear extensions of the tree.
St000094
Ordered trees ⟶ ℤ
The depth of an ordered tree.
St000166
Ordered trees ⟶ ℤ
The depth minus 1 of an ordered tree.
St000167
Ordered trees ⟶ ℤ
The number of leaves of an ordered tree.
St000168
Ordered trees ⟶ ℤ
The number of internal nodes of an ordered tree.
St000328
Ordered trees ⟶ ℤ
The maximum number of child nodes in a tree.
St000397
Ordered trees ⟶ ℤ
The Strahler number of a rooted tree.
St000400
Ordered trees ⟶ ℤ
The path length of an ordered tree.
St000410
Ordered trees ⟶ ℤ
The tree factorial of an ordered tree.
St000413
Ordered trees ⟶ ℤ
The number of ordered trees with the same underlying unordered tree.
St000415
Ordered trees ⟶ ℤ
The size of the automorphism group of the rooted tree underlying the ordered tree....
St000416
Ordered trees ⟶ ℤ
The number of inequivalent increasing trees of an ordered tree.
St000417
Ordered trees ⟶ ℤ
The size of the automorphism group of the ordered tree.
St000521
Ordered trees ⟶ ℤ
The number of distinct subtrees of an ordered tree.
St000522
Ordered trees ⟶ ℤ
The number of 1-protected nodes of a rooted tree.
St000523
Ordered trees ⟶ ℤ
The number of 2-protected nodes of a rooted tree.
St000679
Ordered trees ⟶ ℤ
The pruning number of an ordered tree.
St000700
Ordered trees ⟶ ℤ
The protection number of an ordered tree.
St000973
Ordered trees ⟶ ℤ
The length of the boundary of an ordered tree.
St000974
Ordered trees ⟶ ℤ
The length of the trunk of an ordered tree.
St000975
Ordered trees ⟶ ℤ
The length of the boundary minus the length of the trunk of an ordered tree.

6. Maps

We have the following 11 maps in the database:

Mp00008
Binary trees ⟶ Ordered trees
to complete tree
Mp00010
Binary trees ⟶ Ordered trees
to ordered tree: left child = left brother
Mp00015
Binary trees ⟶ Ordered trees
to ordered tree: right child = right brother
Mp00026
Dyck paths ⟶ Ordered trees
to ordered tree
Mp00046
Ordered trees ⟶ Graphs
to graph
Mp00047
Ordered trees ⟶ Posets
to poset
Mp00048
Ordered trees ⟶ Ordered trees
left-right symmetry
Mp00049
Ordered trees ⟶ Binary trees
to binary tree: left brother = left child
Mp00050
Ordered trees ⟶ Binary trees
to binary tree: right brother = right child
Mp00051
Ordered trees ⟶ Dyck paths
to Dyck path
Mp00139
Ordered trees ⟶ Binary trees
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