22808_TreesandLevels

Trees are everywhere in Computer Science. Traditionally, trees are traversed from the root down, but in this problem you will be concerned with a level-by-level traversal of the tree. A level-order traversal of a tree prints the contents of each node in a given level in left to right order, and all nodes at level k are printed before any nodes at level k+1. For example, for the tree shown in Figure 2, the level-order traversal is 5, 4, 8, 11, 13, 4, 7, 2, 1.

Your job is to read a specification of a binary tree and print out the level-order traversal. The specification is a series of nodes of the form ( n, s ) where n is a node number and s is a string representing the path from the root node. s will consis of a series of L's and R's, where L is for a left branch and R is for a right branch. For example, in the example above the node containing 13 is ( 13, RL ) and the node containing 2 is ( 2, LLR). The root node would be (5, ); there is no path string from the root since it is the root.

A binary tree is completely specified if every node on all root-to-node paths in the tree is given a value exactly once. If the specification dose not specify a complete tree, then your program should display not complete instead of the level-order traversal.

The input is a sequence of binary trees specified as described above. Each tree in a sequence consists of several pairs ( n, s ) as described above, separated by whitespace. The last entry in the tree is ( ). No whitespace appears between left and right parentheses. All nodes contain a positive integer. Every tree in the input will consist of at least one node and no more than 256 nodes.

For each completely specified binary tree in the input, the level order traversal of that tree should be output. If the tree is no completely specified, i.e. some node in the tree is not given a value or a node is given more than one value, then the string not complete should be printed. Each traversal or not complete should appear on a separate line, corresponding to the order of the trees in the input.

(11,LL) (7,LLL) (8,R)
(5,) (4,L) (13,RL) (2,LLR) (1,RRR) (4,RR) ()
(3,L) (4,R) ()

5 4 8 11 13 4 7 2 1
not complete