TAOCP 2.3.2 Exercise 7

Let the partial order on the nodes of a forest be defined by u < v whenever $v$ is a descendant of $u$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.3.2: Binary Tree Representation of Trees

Exercise 7. [M20] A forest may be regarded as a partial ordering, if we say that each node precedes its descendants in the tree. Are the nodes topologically sorted (as defined in Section 2.2.3) when they are listed in (a) preorder? (b) postorder? (c) reverse preorder? (d) reverse postorder?

Verified: yes
Solve time: 1m07s

Solution

Let the partial order on the nodes of a forest be defined by

$$ u < v $$

whenever $v$ is a descendant of $u$. A topological sorting is a linear ordering in which every predecessor appears before every node that succeeds it in the partial order.

We examine each traversal order.

(a) Preorder

The definition of preorder traversal for forests is:

  1. Visit the root of the first tree.
  2. Traverse the subtrees of the first tree.
  3. Traverse the remaining trees.

Every node is therefore visited before any of its descendants. This is proved by induction on the structure of the forest. The root of each tree is visited before traversal enters any subtree, and within each subtree the same property holds recursively.

Hence, if $u$ is an ancestor of $v$, then $u$ appears before $v$ in preorder. Therefore preorder is a topological sorting of the forest.

(b) Postorder

The definition of postorder traversal is:

  1. Traverse the subtrees of the first tree.
  2. Visit the root of the first tree.
  3. Traverse the remaining trees.

Thus every descendant of a node is visited before the node itself. If $u$ is an ancestor of $v$, then $v$ precedes $u$ in postorder.

A topological sorting requires $u$ to precede $v$, so postorder is not, in general, a topological sorting.

For example, a tree consisting of a root $A$ and child $B$ has postorder sequence

$$ B,\ A, $$

while the partial order requires

$$ A < B. $$

Therefore postorder is not a topological sorting.

(c) Reverse preorder

Reverse preorder is obtained by reading the preorder sequence backward.

Since preorder places every ancestor before every descendant, reverse preorder places every descendant before every ancestor.

Using the same two-node tree,

$$ A,\ B $$

is the preorder sequence, so reverse preorder is

$$ B,\ A. $$

This violates the required order $A < B$. Hence reverse preorder is not a topological sorting.

(d) Reverse postorder

Postorder places every descendant before every ancestor. Reversing that sequence places every ancestor before every descendant.

More formally, let $u$ be an ancestor of $v$. In postorder, $v$ precedes $u$. Therefore, in the reversed sequence, $u$ precedes $v$.

Since this holds for every pair related by the partial order, reverse postorder is a topological sorting.

The same conclusion follows from the correspondence stated in Section 2.3.2: postorder on a forest is inorder on the corresponding binary tree. Reversing the postorder sequence therefore reverses every ancestor-descendant relation and yields a valid topological ordering.

Thus:

$$ \boxed{\text{(a) Yes,\quad (b) No,\quad (c) No,\quad (d) Yes.}} $$