TAOCP 2.3.2 Exercise 22

Section 2.3.2: Binary Tree Representation of Trees

Exercise 22. [M26] If T and T' are trees, let us say T can be embedded in T', written T ⊆ T', if there is a one-to-one function f from the nodes of T into the nodes of T' such that f preserves both preorder and postorder. (In other words, u precedes v in preorder for T if and only if f(u) precedes f(v) in preorder for T', and the same holds for postorder. See Fig. 25.)

If T has more than one node, let l(T) be the leftmost subtree of root(T) and let r(T) be the rest of T, that is, T with l(T) deleted. Prove that T can be embedded in T' if (i) T has just one node, or (ii) both T and T' have more than one node and either T ⊆ l(T'), or T ⊆ r(T'), or (l(T) ⊆ l(T') and r(T) ⊆ r(T')). Does the converse hold?

Verified: yes
Solve time: 3m01s

---

Let $P_T$ and $Q_T$ denote the preorder and postorder orderings of the nodes of a tree $T$. By definition, $T\subseteq T'$ if there exists a one-to-one map $f$ from the nodes of $T$ into the nodes of $T'$ such that for all nodes $u,v$ of $T$,

$$ u<{P_T}v \iff f(u)<{P_{T'}}f(v), $$

and

$$ u<{Q_T}v \iff f(u)<{Q_{T'}}f(v). $$

We must prove the stated sufficient conditions and then determine whether they are also necessary.

Sufficiency

Case (i)

If $T$ consists of a single node, map that node to any node of $T'$. Since there are no distinct pairs of nodes in $T$, the preorder and postorder conditions are vacuous. Hence $T\subseteq T'$.

Case (iia)

Assume $T\subseteq l(T')$.

Let $f$ be an embedding of $T$ into $l(T')$. The preorder and postorder relations among nodes of $l(T')$ are the same whether computed in $l(T')$ or in $T'$, because $l(T')$ is a subtree of $T'$. Therefore the same map $f$ is an embedding of $T$ into $T'$. Hence $T\subseteq T'$.

The argument for $T\subseteq r(T')$ is identical.

Case (iib)

Assume

$$ l(T)\subseteq l(T'), \qquad r(T)\subseteq r(T'). $$

Let

$$ f_L:l(T)\to l(T'), \qquad f_R:r(T)\to r(T') $$

be embeddings.

Let $\rho=\operatorname{root}(T)$ and $\rho'=\operatorname{root}(T')$. Define $f$ by

$$ f(\rho)=\rho', $$

by $f=f_L$ on $l(T)$, and by $f=f_R$ on $r(T)$.

Since $l(T)$ and $r(T)$ are disjoint and $f_L,f_R$ are one-to-one, $f$ is one-to-one.

For two nodes both in $l(T)$, preservation of preorder and postorder follows from $f_L$. The same holds for two nodes both in $r(T)$.

Now let $u\in l(T)$ and $v\in r(T)$. Every node of $l(T)$ precedes every node of $r(T)$ in preorder, because the leftmost subtree is traversed completely before the remainder of the tree. The same is true in $T'$. Hence

$$ u<{P_T}v \iff f(u)<{P_{T'}}f(v). $$

Likewise every node of $l(T)$ precedes every node of $r(T)$ in postorder, because the entire leftmost subtree is completed before any node of the remaining subtrees is visited. Therefore

$$ u<{Q_T}v \iff f(u)<{Q_{T'}}f(v). $$

Finally, $\rho$ precedes every other node in preorder and follows every other node in postorder. The same is true of $\rho'$. Thus all comparisons involving the root are preserved.

Hence $f$ is an embedding of $T$ into $T'$, and therefore

$$ T\subseteq T'. $$

This proves the sufficiency of the stated conditions.

The converse

The converse is true.

Assume that

$$ T\subseteq T', $$

and let $f$ be an embedding.

We shall show that one of the three alternatives of (ii) must hold.

A structural lemma

For a node $x$ of a tree $S$, let $S_x$ denote the subtree rooted at $x$.

Lemma

If $x=f(\operatorname{root}(T))$, then every image node $f(v)$ lies in $S_x$.

Proof

Let $r=\operatorname{root}(T)$.

In preorder, $r$ is the first node of $T$. Hence for every $v\neq r$,

$$ r<_{P_T}v. $$

Since $f$ preserves preorder,

$$ x=f(r)<{P{T'}}f(v). $$

Thus every image node other than $x$ occurs after $x$ in preorder.

In postorder, $r$ is the last node of $T$. Hence for every $v\neq r$,

$$ v<_{Q_T}r. $$

Therefore

$$ f(v)<{Q{T'}}x. $$

Thus every image node other than $x$ occurs before $x$ in postorder.

A node $y$ of $T'$ satisfies

$$ x<{P{T'}}y \quad\text{and}\quad y<{Q{T'}}x $$

if and only if $y$ is a proper descendant of $x$. Therefore every $f(v)$ belongs to $S_x$. ∎

Consequence

If $x=f(\operatorname{root}(T))\neq\operatorname{root}(T')$, then $S_x$ is a proper subtree of $T'$.

Every proper subtree of $T'$ lies entirely in either $l(T')$ or $r(T')$. Indeed, every node of $T'$ other than the root belongs either to the leftmost subtree $l(T')$ or to the remainder $r(T')$; since a subtree rooted at a nonroot node cannot contain the root of $T'$, it is contained in whichever of these two parts contains its root.

By the lemma, the image of $T$ is contained in $S_x$. Hence

$$ T\subseteq S_x. $$

Since $S_x\subseteq l(T')$ or $S_x\subseteq r(T')$, we obtain

$$ T\subseteq l(T') \quad\text{or}\quad T\subseteq r(T'). $$

Thus, whenever the root of $T$ does not map to the root of $T'$, one of the first two alternatives holds.

The root-to-root case

It remains to consider the case

$$ f(\operatorname{root}(T)) = \operatorname{root}(T'). $$

Let

$$ A=l(T), \qquad B=r(T), $$

and

$$ A'=l(T'), \qquad B'=r(T'). $$

The nodes of $A$ are characterized inside $T$ by the following property:

$$ u\in A \iff u\neq \operatorname{root}(T) \text{ and } u<{P_T}v,; u<{Q_T}v \text{ for every }v\in B. $$

Indeed, every node of $A$ precedes every node of $B$ in both preorder and postorder, while no node of $B$ has this property.

The same characterization holds for $A'$ inside $T'$.

Take $u\in A$. For every $v\in B$,

$$ u<{P_T}v, \qquad u<{Q_T}v. $$

Applying preservation of preorder and postorder,

$$ f(u)<{P{T'}}f(v), \qquad f(u)<{Q{T'}}f(v) $$

for every $v\in B$.

Hence $f(u)$ has in $T'$ exactly the defining property of a node of $A'$. Therefore

$$ f(u)\in A'. $$

Thus

$$ f(A)\subseteq A'. $$

Since $f$ is injective and the same argument applied to $f^{-1}$ on the image shows that no node of $A$ can map into $B'$, we have

$$ f(A)\subseteq A'. $$

Restricting $f$ to $A$ therefore yields an embedding

$$ A\subseteq A', $$

that is,

$$ l(T)\subseteq l(T'). $$

An entirely symmetric argument shows

$$ r(T)\subseteq r(T'). $$

Therefore the third alternative holds.

-, We have proved that every embedding $T\subseteq T'$ satisfies one of the following:

$$ T\subseteq l(T'), $$

or

$$ T\subseteq r(T'), $$

or

$$ l(T)\subseteq l(T') \quad\text{and}\quad r(T)\subseteq r(T'). $$

Combined with the sufficiency already established, this yields the recursive characterization

$$ T\subseteq T' $$

if and only if either $T$ has one node, or both trees have more than one node and one of the three alternatives above holds.

Hence the converse does hold. ∎