Problem F (ACM ICPC Philippines 2007)

ACM ICPC Philippines 2007
First Philippine National Inter-Collegiate Programming Competition
20 October 2007, De La Salle Canlubang

Problem F: Full Binary Search Tree
(Input File: pf.in)

A full binary tree is a tree in which all non-leaf nodes are filled at every level from left to right except perhaps the last one. A binary search tree is a tree where value stored in the left child node is less than value stored in the parent node and the value stored in the right child node is greater than the value stored in the parent node for all parent nodes.

Figure 1 shows a full binary tree that is also a binary search tree.

Figure 1: Full Binary Search Tree

You are to read a string of numbers then process and print it as a full binary search tree.

Input: The input will contain several test cases. The first line will indicate the number of test cases. Each test case is a string of numbers separated by commas terminated by a 0. We assume that the numbers will be any number from 1 to 99. The string may or may not be arrange and will not contain any duplicate values.

Output: The output shows a full binary search of the string, printed as a triangular shape as shown below.


Sample Input:

2
20, 10, 50, 30, 25, 15, 0
20, 10, 60, 25, 40, 30, 70, 0


Output for the Sample Input:

Case 1:
25
15 50
10 20 30

Case 2:
30
20 60
10 25 40 70