TAOCP 2.3.1 Exercise 36

Let $(S, \prec)$ be a well-ordered set.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.1: Traversing Binary Trees

Exercise 36. [M23] Exercise 1.2.1-15 shows that lexicographic order extends a well-ordering of a set S to a well-ordering of the n-tuples of elements of S. Exercise 25 above shows that a linear ordering of the information in tree nodes can be extended to a linear ordering of trees, using a similar definition. If the relation \prec well-orders S, is the extended relation of exercise 25 a well-ordering of \mathcal{T}?

Verified: no
Solve time: 39s

Solution

Let $(S, \prec)$ be a well-ordered set. That is, every nonempty subset of $S$ has a least element under $\prec$. Let $\mathcal{T}$ denote the set of finite binary trees whose nodes contain elements of $S$. Exercise 25 defines a linear ordering $\prec$ on $\mathcal{T}$ as follows. For $T_1, T_2 \in \mathcal{T}$, write $T_1 \prec T_2$ if and only if

  1. $T_1$ is empty and $T_2$ is nonempty, or
  2. $T_1$ and $T_2$ are both nonempty, with roots $x_1 = \text{INFO}(T_1)$, $x_2 = \text{INFO}(T_2)$, left subtrees $L_1, L_2$, and right subtrees $R_1, R_2$, such that
  • $x_1 \prec x_2$, or
  • $x_1 = x_2$ and $L_1 \prec L_2$, or
  • $x_1 = x_2$, $L_1 = L_2$, and $R_1 \prec R_2$.

This is exactly the lexicographic ordering of the triple $(\text{INFO}(T), L, R)$ using the well-ordering on $S$ and the recursively defined ordering on $\mathcal{T}$.

To show that this ordering is a well-ordering, we must prove that every nonempty subset $\mathcal{U} \subseteq \mathcal{T}$ has a least element. We proceed by induction on the maximum size of trees in $\mathcal{U}$.

Let $\ell(T)$ denote the number of nodes in $T$. Let $m = \min{\ell(T) : T \in \mathcal{U}}$. Then there exists at least one tree $T_0 \in \mathcal{U}$ with $\ell(T_0) = m$. Consider the set of roots of all trees of size $m$ in $\mathcal{U}$:

$$ X = {\text{INFO}(T) : T \in \mathcal{U}, \ell(T) = m}. $$

Since $S$ is well-ordered, $X$ has a least element $x_0$. Let

$$ \mathcal{U}_0 = {T \in \mathcal{U} : \ell(T) = m, \text{INFO}(T) = x_0}. $$

If $\mathcal{U}_0$ contains only one tree, that tree is the least element of $\mathcal{U}$. Otherwise, every tree in $\mathcal{U}_0$ has the same root $x_0$ and the same minimal size $m$. Let

$$ \mathcal{L} = {L : T \in \mathcal{U}_0, L \text{ is the left subtree of } T}. $$

By construction, each $L \in \mathcal{L}$ is strictly smaller than $T$, hence $\ell(L) < m$. By induction on tree size, $\mathcal{L}$ has a least element $L_0$. Define

$$ \mathcal{R} = {R : T \in \mathcal{U}_0, L \text{ is the left subtree of } T, L = L_0, R \text{ is the right subtree of } T}. $$

Again, the trees in $\mathcal{R}$ have size less than $m$, so by induction they have a least element $R_0$. Then the tree $T_{\min}$ with root $x_0$, left subtree $L_0$, and right subtree $R_0$ is the minimal element of $\mathcal{U}$. Indeed, any $T \in \mathcal{U}$ satisfies either $\ell(T) > m$, or $\text{INFO}(T) \succ x_0$, or $L \succ L_0$, or $R \succ R_0$, in which case $T \succ T_{\min}$.

Thus every nonempty subset of $\mathcal{T}$ has a least element under the ordering of Exercise 25. Therefore the extended ordering is a well-ordering.

This completes the proof. ∎