Reconstructing Binary Trees

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.