TAOCP 2.3.1 Exercise 24
No.
Section 2.3.1: Traversing Binary Trees
Exercise 24. [M20] Is Theorem A still valid if the nodes of T and T' are given in symmetric order instead of preorder?
Verified: no
Solve time: 46s
Solution
No.
Theorem A depends essentially on the nodes being listed in preorder. In preorder, the root of every subtree appears before all nodes of that subtree, so the sequence contains enough structural information to determine how the tree is built recursively. This property is lost in symmetric order.
A counterexample suffices. Consider the two binary trees
$$ T= \begin{array}{c} B\ /!!\backslash\ A\qquad C \end{array} $$
and
$$ T'= \begin{array}{c} A\ \backslash\ B\ \backslash\ C \end{array}. $$
The symmetric orders of both trees are
$$ A,\ B,\ C. $$
However, the trees are not similar. In $T$, the root has two children; in $T'$, the root has only a right child. Hence $T$ and $T'$ have different structures.
Therefore any statement asserting, as Theorem A does, that the required structural information can be recovered when the nodes are given in preorder becomes false when preorder is replaced by symmetric order. Symmetric order alone does not determine the structure of a binary tree.
$$ \boxed{\text{Theorem A is not valid when the nodes are given in symmetric order instead of preorder.}} $$