Vamos agora explorar melhor o fato de que, em uma árvore, dois vértices são extremidades de um único caminho. Para tanto, algumas vezes é conveniente considerar um vértice de uma árvore como especial; tal vértice é então chamado de raiz desta árvore.
Para tanto, fixemos $r$ um vértice qualquer de uma árvore $T=(V,A)$. Tal vértice será designado como raiz de $T$ e será utilizado para a definição de uma ordem entre os vértices dessa árvore. Como visto anteriormente,uma árvore com uma raiz fixada é chamada de árvore enraizada. Nesse contexto,escrevemos $x \leq y$ sempre que $x,y \in T$ forem vértices tais que $x \in rTy$, e com isso definimos uma ordenação parcial em $V(T)$, a ordem da árvore associada a $T$ e $r$.Vamos pensar nessa ordenação como expressando "altura" da árvore.
Na figura abaixo, por exemplo, se a raiz da árvore é tomada como o vértice número $4$, tem-se que $2 \leq 3$ e $2 \leq 6$, mas os vértices $0$ e $5$ não podem ser comparados. Note que os vértices $1$ e $2$ também não são comparáveis, mas eles seriam caso a ordem fosse definida se tomássemos o vértice $3$ como raiz. Em outras palavras, a relação $\leq$ depende da escolha da raiz.
Em uma árvore $T=(V,A)$ com raiz $r$, a relação $\leq$ é uma relação de ordem.
Demonstração: Para que esta proposição seja verdadeira precisamos provar as três propriedades de uma relação de ordem: reflexiva$(i)$, anti-simétrica$(ii)$ e transitiva$(iii)$.
$(i)$ Para todo $x \in V$, tem-de trivialmente que $x \in rTx$, isto é, que $x \leq x$. Portanto, a relação $\leq$ é reflexiva;
$(ii)$ Dado $x\in V$, enumere os vértices de $rTx$ como $\{v_0,v_1,\dots,v_n\}$, com $r = v_0$, $x = v_n$ e de modo que, nessa ordem, esses vértices descrevem $rTx$ como caminho. Se $y\in V$ é tal que $y \leq x$, tem-se então que $y = v_i$ para algum $0 \leq i \leq n$. Com isso, o único caminho entre $r$ e $y$ é dado pelos vértices $v_0,v_1,\dots,v_i \in V$ nessa ordem. Assim, caso $x \leq y$, devemos ter $x = v_j$ para algum $1 \leq j \leq i$. Como $j = n$ (pois $x = v_n$), provamos que $i = n$, de modo que $x = y$. Em suma, verificamos que $x = y$ sempre que $x \leq y$ e $y \leq x$. Portanto, a relação $\leq$ é anti-simétrica;
$(iii)$ Suponha que $x,y,z \in V$ são tais que $x \leq y$ e $y \leq z$. Como antes, enumere os vértices do caminho $rTz$ como $\{v_0,v_1,\dots,v_n\}$ com $v_0 = r$, $v_n = z$ e de modo que, nessa ordem, esses vértices descrevem $rTz$ como caminho. Como $y \in rTz$, tem-se que $y = v_k$ para algum $0 \leq k \leq n$. Assim, $rTy$ é o subcaminho formado pelos vértices $v_0,v_1,v_2,\dots,v_k$. Dado que $x\in rTy$, tem-se que $x = v_i$ para algum $0 \leq i \leq k$. Em particular, $x\in rTz$, provando que $x \leq z$. Portanto, a relação $\leq$ é transitiva.
$\square$
Além disso, algumas definições e notações são utilizadas com frequência para descrever certas propriedades da ordem de uma árvore. Juntamente com algumas observações pertinentes, listamos abaixo essas principais convenções a respeito de uma árvore $T = (V,A)$ (com a ordem obtida pela escolha de uma raiz $r\in V$):
Observe disso que a raiz de $T$ é o menor elemento em relação a sua ordem na árvore, isto é, a altura da raiz é a menor em todos os vértices da árvore;por outro lado, as folhas são seus elementos máximos. Além disso, as extremidades de qualquer aresta de $T$ são comparáveis e a linha descendente de cada vértice é uma cadeia, um conjunto de pares de elementos comparáveis. Os vértices à distância $k$ da raiz têm altura e formam o $k$-ésimo nível de $T$.