Falling Leaves

Consider the following operation on a binary search tree whose nodes are single capital letters.

• Remove every leaf of the tree at once and list the letters that were removed.
• Repeat until the tree is empty.

Starting from the tree on the left below, we obtain the sequence of trees shown and finally the empty tree.

In this example the leaves removed at each stage are, in order, BDHPY, then CM, then GQ, and finally K.

You are given such a sequence of lines of leaves produced by repeatedly removing the leaves of a binary search tree of letters. Reconstruct the tree and output its preorder traversal.

The input consists of one or more data sets. Each data set is a sequence of one or more lines of capital letters, giving the leaves removed from a binary search tree in the stages described above. The letters on a line are listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk (*). The last data set is followed by a line containing only a dollar sign ($). There are no blanks or empty lines in the input.

For each data set there is a unique binary search tree that would produce that sequence of leaves. Output one line containing only the preorder traversal of that tree, with no blanks.