떨어지는 잎

글자를 노드로 가지는 이진 탐색 트리(binary search tree)에 대해 다음 연산을 생각하자.

• 트리의 모든 잎(leaf) 노드를 한꺼번에 제거하고, 제거한 글자들을 기록한다.
• 트리가 빌 때까지 이 과정을 반복한다.

아래 왼쪽 트리에서 시작하면 그림과 같은 트리들의 수열을 거쳐 마지막에는 빈 트리에 도달한다.

이 예에서 각 단계에 제거되는 잎의 글자는 순서대로 BDHPY, 그다음 CM, 그다음 GQ, 마지막으로 K이다.

이처럼 어떤 글자 이진 탐색 트리에서 잎을 반복적으로 제거하며 얻은 글자 줄들의 수열이 주어진다. 원래 트리를 복원하여 그 트리의 전위 순회(preorder traversal) 결과를 출력하라.

입력은 하나 이상의 데이터 집합으로 이루어진다. 각 데이터 집합은 대문자로 이루어진 한 줄 이상의 줄들이며, 위에서 설명한 각 단계에서 이진 탐색 트리에서 제거된 잎을 나타낸다. 한 줄 안의 글자들은 알파벳 오름차순으로 나열된다. 데이터 집합들은 별표(*) 하나만 있는 줄로 구분되고, 마지막 데이터 집합 뒤에는 달러 기호($) 하나만 있는 줄이 온다. 입력에는 공백이나 빈 줄이 없다.

각 데이터 집합에 대해, 그 잎 수열을 만들어 낼 수 있는 이진 탐색 트리는 유일하다. 해당 트리의 전위 순회 결과를 공백 없이 한 줄에 출력하라.