TAOCP 2.3.2 Exercise 20

Let $F$ be a forest and let $u, v$ be nodes in $F$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 20. [M22] Prove that if u and v are nodes of a forest, u is a proper ancestor of v if and only if u precedes v in preorder and u follows v in postorder.

Verified: yes
Solve time: 1m22s

Solution

Let $F$ be a forest and let $u, v$ be nodes in $F$. We aim to prove that $u$ is a proper ancestor of $v$ if and only if $u$ precedes $v$ in preorder and $u$ follows $v$ in postorder. The proof proceeds in two directions.

(⇒) If $u$ is a proper ancestor of $v$, then $u$ precedes $v$ in preorder and follows $v$ in postorder.

Suppose $u$ is a proper ancestor of $v$ in $F$. By definition, there exists a sequence of nodes $u = w_0, w_1, \dots, w_k = v$ such that each $w_i$ is the parent of $w_{i+1}$, and $k \ge 1$. Consider the preorder traversal of $F$. Preorder visits a node before visiting any of its descendants. Therefore, since $u = w_0$ is an ancestor of $v = w_k$, the traversal visits $u$ before $w_1$, $w_2$, …, up to $v$. Consequently, $u$ precedes $v$ in preorder.

Next, consider the postorder traversal of $F$, defined so that a node is visited after all its descendants have been traversed. Since $v$ is a descendant of $u$, all descendants of $u$, including $v$, are visited before $u$ itself. Therefore, $u$ follows $v$ in postorder.

This establishes the forward direction.

(⇐) If $u$ precedes $v$ in preorder and follows $v$ in postorder, then $u$ is a proper ancestor of $v$.

Suppose $u$ precedes $v$ in preorder and follows $v$ in postorder. Let $T$ be the tree in $F$ containing $u$ and $v$. If $u$ and $v$ were in different trees of the forest, preorder traversal would visit all nodes of the tree containing $u$ before any node of the tree containing $v$. In that case, $u$ would precede $v$ in both preorder and postorder, contradicting the assumption that $u$ follows $v$ in postorder. Therefore, $u$ and $v$ lie in the same tree $T$.

Let $\operatorname{pre}(x)$ and $\operatorname{post}(x)$ denote the positions of node $x$ in preorder and postorder, respectively. Consider the sequence of nodes along the unique path from $u$ to $v$ in $T$. Let $w_0 = u, w_1, \dots, w_m = v$ be this path, with each $w_i$ the parent of $w_{i+1}$.

If $u$ were not an ancestor of $v$, then either $v$ is an ancestor of $u$ or $u$ and $v$ are incomparable (i.e., neither is an ancestor of the other).

  • If $v$ is an ancestor of $u$, preorder visits $v$ before $u$, contradicting the assumption that $u$ precedes $v$ in preorder.
  • If $u$ and $v$ are incomparable, let $w$ be their least common ancestor. Preorder visits $w$ before $u$ and $v$, and visits $u$ before $v$ if $u$ is to the left of $v$. Postorder visits $w$ after both $u$ and $v$. Therefore, for incomparable nodes $u$ and $v$, preorder and postorder both respect the left-to-right order of subtrees. Since $u$ precedes $v$ in preorder, postorder must also visit $u$ before $v$, contradicting the assumption that $u$ follows $v$ in postorder.

Thus, the only possibility is that $u$ is a proper ancestor of $v$.

-, Both directions have been established, completing the equivalence: $u$ is a proper ancestor of $v$ if and only if $u$ precedes $v$ in preorder and follows $v$ in postorder.

This completes the proof.

∎