Problem 5: Binary Tree Levels

Background:

Trees are important data structures for computer scientists. Unfortunately, since CS people don't get outside very much, they've developed a habit of drawing their trees upside down.

A binary tree is one where each node has, at most, 2 children, creatively named left and right. We define the level of a tree as the number of parent nodes a tree node has. The root of the tree, therefore, is at level 0. Root's children are at level 1, etc. In general, each level of a binary tree can have, at most, 2N nodes, where N is the level of the tree. To be counted as a level, the level must have at least one non-null node. The maximum level of the tree is the last such level.

As an example, consider the tree: 

                   A
                  /  \
                 1    2
                / \    \
               3   4    C
                         \
                          D
At level 2, the tree has the elements 3, 4, and C. The maximum level of the tree is 3.

For this problem, you'll be given a tree and asked to print out all members of the tree at a given level.

Input:

Each test case consists of a number N, followed by the tree. The tree is of the form (root left right), where left and right are the subtrees and root is the root of the tree. Note the definition is recursive. root is one printable character, excluding ( and ). An empty tree is given by (). A tree will be fully specified. The tree above would be given as (A(1(3()())(4()()))(2()(C()(D()())))).

There is an arbitrary amount of space between any two characters of the tree. No single line of input will be more than 80 characters. However, the tree can span multiple lines. Obviously, a tree ends when the () have been balanced. Each test case will always start on a new line.

Oh, one more thing. In the spirit of previous ACM contests, the tree may be arbitrarily long.

Output:

READ CAREFULLY For this problem, the following output specifications must be followed correctly. If you add in extra spaces, you will get a failed submission (something along the lines of Presentation Error).

For the given level, print out the elements of the tree found on that level. They should appear in the exact same order as they would if you had manually drawn the tree and read off the elements from left to right.

Print the element followed by exactly one space. If a node is empty on that level, then print exactly two spaces (one space for where the node would have been and one space following the node). Empty nodes should be printed only if they have a parent node on the previous level. In other words, don't fill in any values for the "children" of a leaf node. When all the nodes on a given level have been printed, print a newline. Note that this will mean there is one space at the end of line.

If the given level is larger than the maximum level of the tree, then print "No such level" (without the quotes).

Sample Input:

2 (A (1 (3 () ()) (4 ()())) (2 ()(C ()(D ()()))))
3 (A (1 (3 () ()) (4 ()())) (2 ()(C ()(D ()()))))
10 (A (1 (3 () ()) (4 ()())) (2 ()(C ()(D ()()))))
2 (A()
(B ()
(C ()
(D () ()))))

Sample Output:

(Note that in order to better show the spacing for this problem, - have replaced the spaces in the sample output. Your solutions should print spaces, and not the -.)

3-4---C-
----------D-
No-such-level
--C-