# ordered tree

A tree is, by definition, a partially ordered set. An ordered tree is a tree equipped with a linear extension. In other words, its a linear order on the nodes of the tree that obeys the parent-child relationship of the tree. By Zorn’s lemma, every tree can be ordered. When a tree $T$ is finite, the linear extension of the tree can be constructed inductively:

1. 1.

First, label the nodes of $T$: each label is an $n$-tuple of positive integers, for some $n$,

1. (a)

the root of $T$ is labeled $(1)$,

2. (b)

if a node $V$ of $T$ has been labeled $(m_{1},\ldots,m_{k})$, and if the children of $T$ are $V_{1},\ldots,V_{\ell}$, then label each $V_{i}$ by $(m_{1},\ldots,m_{k},i)$.

From this labeling process, we see that the (direct) children of the root have labels $(1,1),(1,2),\ldots$. In general, if a node is of level $k$, its label is a $k$-tuple starting with $1$. It is easy to see that each label corresponds to a unique node of $T$: for if two distinct nodes are of different level, their labels are clearly different. However, if they are of the same level, then the last components of their labels are distinct.

2. 2.

Next, order the labels of the nodes lexicographically. In other words, given an $m$-tuple $p=(p_{1},\ldots,p_{m})$ and an $n$-tuple $q=(q_{1},\ldots,q_{n})$, compare them componentwise, starting from the first. There are two cases:

1. (a)

either all $k$ components match, where $k=\min(m,n)$, or

2. (b)

$p_{j}\neq q_{j}$, but $p_{i}=q_{i}$ for all $i, where $j\leq\min(m,n)$.

Then $p iff $m in the first case, or $p_{j} in the second. This ordering on the labels induces an ordering on the nodes: for nodes $V$ and $V^{\prime}$ with labels $p$ and $p^{\prime}$,

 $V\leq V^{\prime}\qquad\mbox{iff}\qquad p\leq p^{\prime}.$

This ordering on the nodes is linear, and extends the partial ordering on $T$.

For example, below are two diagrams of the same tree. The one on the right is labeled by the method above:

By ordering the labels, we get the corresponding ordering of the nodes:

 $a
Title ordered tree OrderedTree 2013-03-22 19:00:11 2013-03-22 19:00:11 CWoo (3771) CWoo (3771) 5 CWoo (3771) Definition msc 03E05