Reconstructing Faulty Tree Traversals

Anatoly Cheng McDougal, a student known for his cut‐and‐paste coding habits, submitted three tree traversal routines – prePrint, inPrint and postPrint – that were meant to print a binary tree in preorder, inorder, and postorder respectively. Unfortunately, after copying and modifying the original code, he erroneously changed some of the recursive calls. Although the output statement in each routine remained in the correct location, among the six recursive calls (two in each routine) exactly two call prePrint, two call inPrint and two call postPrint (but they may now be in the wrong routines).

The professor, upon observing the three output strings produced when each routine was executed on the test tree, made two assumptions:

1. The output statement in each routine is in its proper place (for example, in the inorder print, the output is printed between the two recursive calls).
2. Among the six recursive calls, there are exactly 2 calls to each of the three routines.

Your task is to help reconstruct all possible assignments of the recursive call functions (which we denote by f1 to f6) that are consistent with the observed output. In addition, for each reconstruction you must find the alphabetically smallest binary tree that produces the three given output strings.

The routines can be described by the following formulas in LaTeX:

\[ \text{prePrint}(t) = t.value \;\|\; F_{f_1}(t.left) \;\|\; F_{f_2}(t.right), \]

\[ \text{inPrint}(t) = F_{f_3}(t.left) \;\|\; t.value \;\|\; F_{f_4}(t.right), \]

\[ \text{postPrint}(t) = F_{f_5}(t.left) \;\|\; F_{f_6}(t.right) \;\|\; t.value, \]

where for any function \(f\) (one of prePrint, inPrint, or postPrint), \(F_{f}(t)\) denotes calling that function on tree \(t\), and \(\|\) denotes string concatenation. The mapping \(f_1, f_2, \ldots, f_6\) is a permutation with exactly two occurrences of each of the three functions.

The binary tree is represented in the following format: a node is written as value(left,right), where left and right are the representations of its left and right subtrees respectively (an empty subtree is denoted by an empty string). When comparing trees, the lexicographical (i.e. alphabetical) order of these string representations is used; you are to output the alphabetically first tree among all those producing the given outputs.

inputFormat

The input consists of three lines:

• The first line is the output produced by prePrint on the test tree.
• The second line is the output produced by inPrint.
• The third line is the output produced by postPrint.

Each output is a non-empty string of characters.

outputFormat

Output first an integer k indicating the number of valid reconstructions. Then for each reconstruction, output two lines:

• The first line contains six space-separated tokens representing the assignment for recursive calls f1 to f6 (each token is either pre, in, or post).
• The second line contains the alphabetically smallest binary tree (represented as value(left,right)) that produces the given traversals.

sample

A
A
A

1
pre pre in in post post
A