TAOCP 2.3.1 Exercise 26

Let $D(T)$ denote the double-order sequence of a binary tree $T$, as defined in exercise 18.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.1: Traversing Binary Trees

Exercise 26. [M24] Consider the ordering T \preceq T' defined in the preceding exercise. Prove a theorem analogous to Theorem A, giving a necessary and sufficient condition that T \preceq T', and making use of double order as defined in exercise 18.

Verified: no
Solve time: 59s

Solution

Let $D(T)$ denote the double-order sequence of a binary tree $T$, as defined in exercise 18. In double order, each node appears twice: once when first encountered and once when encountered again after traversal of its left subtree. Thus, if $T$ has $n$ nodes, $D(T)$ contains $2n$ terms.

Exercise 25 defines the ordering $\preceq$ recursively by comparing roots first, then left subtrees, and finally right subtrees. This is precisely a lexicographic comparison of the triples

$$ (\operatorname{info}(\operatorname{root}(T)), \operatorname{left}(T), \operatorname{right}(T)). $$

The analogue of Theorem $A$ is therefore obtained by expressing this recursive comparison directly in terms of the double-order sequence.

Theorem. Let $T$ and $T'$ be binary trees whose node information belongs to the linearly ordered set $S$. Form the double-order sequences

$$ D(T)=a_1,a_2,\ldots,a_{2m}, \qquad D(T')=b_1,b_2,\ldots,b_{2n}. $$

Then $T\preceq T'$ if and only if either

  1. $D(T)$ is empty; or
  2. there exists an index $k$ such that

$$ a_i=b_i \qquad (1\le i<k), $$

and

$$ a_k\prec b_k; $$

or

  1. $D(T)$ is an initial segment of $D(T')$.

In other words, $T\preceq T'$ if and only if the double-order sequences are ordered lexicographically.

We prove both directions.

Assume first that $T\preceq T'$. Proceed by induction on the total number of nodes in $T$ and $T'$.

If $T$ is empty, $D(T)$ is empty, and condition 1 holds.

Suppose that $T$ and $T'$ are nonempty. Let

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

The double-order sequence begins with the root information. Hence

$$ D(T)=r,\ D(L),\ r,\ D(R), $$

$$ D(T')=r',\ D(L'),\ r',\ D(R'), $$

where $L,R$ and $L',R'$ are the left and right subtrees.

If $r\prec r'$, the first terms of the two double-order sequences already differ, and $D(T)$ is lexicographically smaller.

Suppose $r=r'$. If $L\preceq L'$ and $L$ is not equivalent to $L'$, exercise 25 places $T\preceq T'$ because of the left subtrees. By the induction hypothesis, $D(L)$ is lexicographically smaller than $D(L')$. Since both double-order sequences begin with the same root entry $r$, their first difference occurs within the portions $D(L)$ and $D(L')$. Therefore $D(T)$ is lexicographically smaller than $D(T')$.

Suppose $r=r'$ and $L$ is equivalent to $L'$. Then $D(L)=D(L')$ by Theorem $A$. The second occurrence of the root is therefore reached simultaneously in both sequences. Exercise 25 then compares $R$ and $R'$. By the induction hypothesis, $D(R)$ is lexicographically not greater than $D(R')$. Consequently $D(T)$ is lexicographically not greater than $D(T')$.

Thus $T\preceq T'$ implies that $D(T)$ precedes $D(T')$ lexicographically.

Conversely, assume that $D(T)$ is lexicographically not greater than $D(T')$. Again proceed by induction.

If $D(T)$ is empty, then $T$ is empty and $T\preceq T'$ by definition.

Suppose both trees are nonempty. The first terms of the double-order sequences are the root information values $r$ and $r'$.

If $r\prec r'$, condition 2 of exercise 25 gives $T\preceq T'$.

Suppose $r=r'$. The next portions of the double-order sequences are $D(L)$ and $D(L')$. If the first lexicographic difference occurs within these portions, the induction hypothesis yields $L\preceq L'$ with $L$ not equivalent to $L'$. Hence condition 3 of exercise 25 gives $T\preceq T'$.

If $D(L)=D(L')$, then Theorem $A$ implies that $L$ and $L'$ are equivalent. The next comparison occurs in $D(R)$ and $D(R')$. By the induction hypothesis, $R\preceq R'$. Therefore condition 4 of exercise 25 gives $T\preceq T'$.

Thus lexicographic comparison of the double-order sequences implies $T\preceq T'$.

The two implications establish the theorem. Therefore $T\preceq T'$ exactly when the double-order sequence of $T$ precedes the double-order sequence of $T'$ in lexicographic order.

This completes the proof.

∎

Notes

The reason double order is required is that, by Theorem $A$, a binary tree is uniquely determined by its double-order sequence. Hence the recursive comparison of roots, left subtrees, and right subtrees can be translated into an ordinary lexicographic comparison of those sequences. Preorder alone would not suffice, because preorder does not determine the tree uniquely.