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 parentchild 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.
First, label the nodes of $T$: each label is an $n$tuple of positive integers, for some $n$,

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

(b)
if a node $V$ of $T$ has been labeled $({m}_{1},\mathrm{\dots},{m}_{k})$, and if the children of $T$ are ${V}_{1},\mathrm{\dots},{V}_{\mathrm{\ell}}$, then label each ${V}_{i}$ by $({m}_{1},\mathrm{\dots},{m}_{k},i)$.
From this labeling process, we see that the (direct) children of the root have labels $(1,1),(1,2),\mathrm{\dots}$. 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.

(a)

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

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

(b)
${p}_{j}\ne {q}_{j}$, but ${p}_{i}={q}_{i}$ for all $$, where $j\le \mathrm{min}(m,n)$.
Then $$ iff $$ in the first case, or $$ 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\le {V}^{\prime}\mathit{\hspace{1em}\hspace{1em}}\text{iff}\mathit{\hspace{1em}\hspace{1em}}p\le {p}^{\prime}.$$ This ordering on the nodes is linear, and extends the partial ordering on $T$.

(a)
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:
$$ 
Title  ordered tree 

Canonical name  OrderedTree 
Date of creation  20130322 19:00:11 
Last modified on  20130322 19:00:11 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  5 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 03E05 