TAOCP 2.3.1 Exercise 25

Section 2.3.1: Traversing Binary Trees

Exercise 25. [M24] Let \mathcal{T} be a set of binary trees in which the value of each info field belongs to a given set S, where S is linearly ordered by a relation "\preceq" (see exercise 2.2.3-14). Given any trees T, T' in \mathcal{T}, let us now define T \preceq T' if and only if

T is empty; or
T and T' are not empty, and \operatorname{info}(\operatorname{root}(T)) \prec \operatorname{info}(\operatorname{root}(T')); or
T and T' are not empty, \operatorname{info}(\operatorname{root}(T)) = \operatorname{info}(\operatorname{root}(T')), \operatorname{left}(T) \preceq \operatorname{left}(T'), and \operatorname{left}(T) is not equivalent to \operatorname{left}(T'); or
T and T' are not empty, \operatorname{info}(\operatorname{root}(T)) = \operatorname{info}(\operatorname{root}(T')), \operatorname{left}(T) is equivalent to \operatorname{left}(T'), and \operatorname{right}(T) \preceq \operatorname{right}(T').

Here \operatorname{left}(T) and \operatorname{right}(T) denote the left and right subtrees of T. Prove that (a) T \preceq T' and T' \preceq T'' implies T \preceq T''; (b) T is equivalent to T' if and only if T \preceq T' and T' \preceq T; (c) for any T, T' in \mathcal{T} we have either T \preceq T' or T' \preceq T. [Thus, if equivalent trees in \mathcal{T} are regarded as equal, the relation \preceq induces a linear ordering on \mathcal{T}. This ordering has many applications (for example, in the simplification of algebraic expressions). When S has only one element, so that the "info" of each node is the same, we have the special case that equivalence is the same as similarity.]

Verified: no
Solve time: 52s

Solution

We first interpret the definition of $\preceq$ as a recursive lexicographic comparison of trees: the empty tree precedes every tree; among nonempty trees, the roots are compared first; if the roots agree, the left subtrees are compared; if the left subtrees are equivalent, the right subtrees are compared.

Let $\equiv$ denote equivalence of trees, namely, mutual comparability:

$$ T \equiv T' \quad\text{means}\quad T \preceq T' \text{ and } T' \preceq T. $$

We shall prove simultaneously, by induction on the total number of nodes of the trees involved, that statements (a), (b), and (c) hold.

Let

$$ N(T,T',T'') = |T|+|T'|+|T''|, $$

where $|T|$ denotes the number of nodes of $T$.

When all trees are empty, every statement is immediate from clause 1 of the definition.

Assume the assertions hold whenever the total number of nodes is less than $N$, and consider trees with total $N$ nodes.

(a) Transitivity

Assume

$$ T \preceq T', \qquad T' \preceq T''. $$

We must prove

$$ T \preceq T''. $$

If $T$ is empty, clause 1 gives $T \preceq T''$ immediately.

Assume $T$ is nonempty. Since $T \preceq T'$, tree $T'$ is also nonempty. Since $T' \preceq T''$, tree $T''$ is nonempty.

Let

$$ a=\operatorname{info}(\operatorname{root}(T)), \qquad b=\operatorname{info}(\operatorname{root}(T')), \qquad c=\operatorname{info}(\operatorname{root}(T'')). $$

There are three possibilities.

$$ a \prec b, $$

then from $T' \preceq T''$ we have either $b \prec c$ or $b=c$, since $T'$ is nonempty. By transitivity of the linear order on $S$,

$$ a \prec c. $$

Hence clause 2 gives

$$ T \preceq T''. $$

$$ a=b $$

and

$$ \operatorname{left}(T)\precceq \operatorname{left}(T') $$

with

$$ \operatorname{left}(T)\not\equiv \operatorname{left}(T'), $$

then $T' \preceq T''$ implies either $b\prec c$, in which case $a\prec c$ and clause 2 applies, or $b=c$.

In the case $b=c$, write

$$ L=\operatorname{left}(T), \quad L'=\operatorname{left}(T'), \quad L''=\operatorname{left}(T''). $$

Since

$$ L \preceq L', \qquad L' \preceq L'', $$

the induction hypothesis gives

$$ L \preceq L''. $$

Suppose for contradiction that

$$ L \equiv L''. $$

Then, by part (b) of the induction hypothesis,

$$ L'' \preceq L. $$

Since $L' \preceq L''$, transitivity for smaller trees yields

$$ L' \preceq L. $$

Together with $L \preceq L'$, part (b) for smaller trees gives

$$ L \equiv L', $$

contrary to hypothesis. Therefore

$$ L\not\equiv L''. $$

Clause 3 now gives

$$ T \preceq T''. $$

Finally, suppose

$$ a=b, \qquad \operatorname{left}(T)\equiv \operatorname{left}(T'), $$

and

$$ \operatorname{right}(T)\preceq \operatorname{right}(T'). $$

If $b\prec c$, clause 2 applies immediately.

If $b=c$, then $T' \preceq T''$ yields either clause 3 or clause 4. Let

$$ L=\operatorname{left}(T), \quad L'=\operatorname{left}(T'), \quad L''=\operatorname{left}(T''). $$

Since

$$ L\equiv L', $$

part (b) of the induction hypothesis gives

$$ L\preceq L', \qquad L'\preceq L. $$

If clause 3 applies to $T' \preceq T''$, then

$$ L' \preceq L'', \qquad L' \not\equiv L''. $$

Transitivity for smaller trees gives

$$ L\preceq L''. $$

If $L\equiv L''$, then $L''\preceq L$, and since $L'\preceq L''$ we obtain $L'\preceq L$, hence $L\equiv L'$, contradicting $L'\not\equiv L''$. Thus

$$ L\not\equiv L'', $$

and clause 3 gives

$$ T\preceq T''. $$

If clause 4 applies to $T' \preceq T''$, then

$$ L'\equiv L'', $$

and

$$ R' \preceq R'', $$

where $R,R',R''$ denote the right subtrees. Since

$$ L\equiv L', \qquad L'\equiv L'', $$

part (b) for smaller trees and transitivity imply

$$ L\equiv L''. $$

Also,

$$ R\preceq R', \qquad R'\preceq R'', $$

so the induction hypothesis gives

$$ R\preceq R''. $$

Clause 4 therefore yields

$$ T\preceq T''. $$

This proves transitivity.

(b) Characterization of equivalence

Assume first that

$$ T\equiv T'. $$

By definition,

$$ T\preceq T', \qquad T'\preceq T. $$

Conversely, assume

$$ T\preceq T', \qquad T'\preceq T. $$

We prove that $T$ and $T'$ are equivalent in the ordinary structural sense.

If one tree is empty, clause 1 forces the other to be empty also.

Assume both are nonempty. Let

$$ a=\operatorname{info}(\operatorname{root}(T)), \qquad b=\operatorname{info}(\operatorname{root}(T')). $$

Neither relation can arise from clause 2, since $a\prec b$ and $b\prec a$ cannot both hold in a linear order. Therefore

$$ a=b. $$

Let

$$ L=\operatorname{left}(T), \qquad L'=\operatorname{left}(T'). $$

If clause 3 held for one comparison, say

$$ L\preceq L', \qquad L\not\equiv L', $$

then from $T'\preceq T$ we would have either $L'\preceq L$ or $L'\equiv L$ together with comparison of right subtrees. In either case, by induction and transitivity,

$$ L\equiv L', $$

a contradiction. Hence clause 3 cannot occur.

Therefore both comparisons must arise from clause 4. Consequently,

$$ L\equiv L', $$

and if

$$ R=\operatorname{right}(T), \qquad R'=\operatorname{right}(T'), $$

then

$$ R\preceq R', \qquad R'\preceq R. $$

The induction hypothesis yields

$$ R\equiv R'. $$

Thus the roots agree, the left subtrees are equivalent, and the right subtrees are equivalent. Hence

$$ T\equiv T'. $$

(c) Comparability

We prove that for any $T,T'$,

$$ T\preceq T' \quad\text{or}\quad T'\preceq T. $$

If one tree is empty, clause 1 applies.

Assume both are nonempty, and let

$$ a=\operatorname{info}(\operatorname{root}(T)), \qquad b=\operatorname{info}(\operatorname{root}(T')). $$

Since $S$ is linearly ordered, exactly one of the following holds:

$$ a\prec b, \qquad a=b, \qquad b\prec a. $$

$$ a\prec b, $$

clause 2 gives

$$ T\preceq T'. $$

$$ b\prec a, $$

clause 2 gives

$$ T'\preceq T. $$

Assume

$$ a=b. $$

Let

$$ L=\operatorname{left}(T), \qquad L'=\operatorname{left}(T'). $$

By induction,

$$ L\preceq L' \quad\text{or}\quad L'\preceq L. $$

$$ L\preceq L' $$

and

$$ L\not\equiv L', $$

clause 3 gives

$$ T\preceq T'. $$

$$ L'\preceq L $$

and

$$ L'\not\equiv L, $$

clause 3 gives

$$ T'\preceq T. $$

The remaining case is

$$ L\equiv L'. $$

Let

$$ R=\operatorname{right}(T), \qquad R'=\operatorname{right}(T'). $$

By induction,

$$ R\preceq R' \quad\text{or}\quad R'\preceq R. $$

Clause 4 then gives respectively

$$ T\preceq T' \quad\text{or}\quad T'\preceq T. $$

Therefore every pair of trees is comparable.

This completes the proof.

∎