Write a program that sorts the given integer values. The number of values is not known in advance. Your program will output the sorted values and the structure of the tree using given output format. (Assume for this homework study, values are distinct). Use red-black tree in your program.

Input:

72

18

28

36

27

117

108

90

-1

Your output will be the sorted list of given numbers (In-order walk on red-black tree produce the sorted list).

Your program should print the red-black tree in the following way (First number represents the value, the letter displays the color (R for red and B for black) and the number and the letter in parenthesis shows the parent node. L represents left child and R represents right child). Null nodes (leaf nodes) will not be printed.

28 B

18 (28 L) 72 (28 R)

27 (18 R) 36 (72 L) 108 (72 R)

90 (108 L) 117 (108 R)

Output:

18

27

28

36

72

90

108

127

28 B

18 (28 L) 72 (28 R)

27 (18 R) 36 (72 L) 108 (72 R)

90 (108 L) 117 (108 R)