Reconstructing Binary Trees

Time limit1sMemory limit128 MB

Summary

Given the pre-order and in-order traversals of a binary tree with distinct labels, print its post-order traversal or report that no tree matches.

Level: Medium5 of 10
Topics: Tree, Recursion, Divide and conquer, Hash map
Solved: No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

Example 1
Input
```
EDBACFGIHKJ ABCDEFGHIJK
#
```
Expected output
```
ACBDHJKIGFE
```