Generating the various traversals of a binary tree is easy; this problem asks for the reverse. Given the pre-order and in-order traversals of a binary tree (not necessarily a binary search tree), reconstruct the original tree and output its post-order traversal, provided such a tree exists.
For example, the tree below yields the traversals shown:
E
/ \
D F
/ \
B G
/ \ \
A C I
/ \
H K
/
J
Preorder : EDBACFGIHKJ
Inorder : ABCDEFGHIJK
Postorder: ACBDHJKIGFE
Because every node label is distinct, a pair of pre-order and in-order traversals identifies at most one binary tree.
The input describes several trees, one per line, and ends with a line containing a single #.
Each tree line holds two space-separated strings made of up to 26 distinct uppercase letters: the pre-order traversal followed by the in-order traversal.
<pre-order> <in-order>
On every line the two strings are guaranteed to be permutations of each other.
For each tree, print the post-order traversal of the reconstructed tree on its own line. If no binary tree matches the given traversals, print Invalid tree instead.