Problem: binstree

Problem IDbinstree
Difficulty level (0..10)3
Maximum runtime1 minute
Original problemgreece96_problem3.html
Seen atFirst Hellenic Internet Programming Contest

String Searching

A binary search tree is used to search for data strings of lowercase alphabetic characters (a-z). Each tree node, v, holds a data string, v(s). All strings stored in the left subtree of v are lexicographically smaller than v(s), whereas all strings in the right subtree of v are lexicographically larger than v(s). Also, no string is present in the tree more than once. The binary search tree supports insertions and deletions.

Assume that we have a set of strings s1, s2, ..., sn (n<=100), where each string comprises of 10 characters at most. The problem is to build a binary search tree incrementally, inserting one string at a time. Evidently, the tree is not balanced in the general case.

Input
Your program should read the input from the standard input, which has the following format.

Output
Your program should produce the output in the standard output, which should have the following format.

Sample input:

7
door
ace
ace
external
extension
cat
flight

Sample output:

2 8
ROOT
L
EXISTS
R
RL
LR
RR