Woburn Challenge 2001

Problem 2: The Island of Dr. Strangelove

There’s a problem. After following his map to what should have been the Okagor camp, Mason realizes that the mission will fail, for he has landed on Temptation Island, not Survivor Island. Since John Patrick Mason bears a passing resemblance to Sean Connery, he is quickly surrounded by a bevy of women who are quite forthcoming with their phone numbers. Pulling out his standard issue SAS black book, Mason quickly jots down the numbers he is being given. But what if he is captured by the men’s camp…who knows what havoc would be wreaked if the phone numbers fell into their hands. As a result, he encrypts the number using a simple method that reckons back to his computer science days at Seton Hall. He considers the digits of the phone number to represent the postfix traversal of a binary search tree (see next page for an explanation of binary search trees). He encrypts them by writing down the prefix traversal of the same tree. Later that evening, someone in the men’s camp steals Mason’s black book and tries to decrypt the information. Immediately recognizing the code as a post-to-prefix encryption he sets about decrypting the phone numbers.

Each phone number is a series of positive integers no greater than 32767 (each “digit” is an integer) and no phone number contains any duplicate digits.

Your job is to decrypt a series of numbers (convert them back from prefix to postfix). Although it is guaranteed that the digits are distinct, for some inputs a search tree with the desired prefix traversal cannot be formed. If so, print out No such tree; otherwise, print out the decryption, i.e. the postfix traversal of the same tree. Note that with the installation of new area codes, the phone numbers can be up to 500 “digits” long.


The first line of the input contains T, the number of test cases.Each of the T remaining lines of the input will contain a phone number encoded using Mason’s post-to-prefix method: the first digit on the line is N, the number of digits in the phone number (1 ≤ N ≤ 500) and following that is the encoded phone number itself.


For each input, output either the decoded phone number, or No such tree.

Sample Input

7 4 2 1 3 6 5 7
8 6 2 1 4 8 9 11 10
5 9 7 12 5 11

Sample Output

1 3 2 5 7 6 4
1 4 2 10 11 9 8 6
No such tree

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Nov 23, 2008

Languages Allowed:

Comments (Search)

It's quiet in here...