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:

# 6. Maps

We have the following **11 maps** in the database:

# 7. References

*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