Problem: binstree

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 s₁, s₂, ..., s_n (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.

• The first line contains the number of strings, n, to be inserted in the binary search tree, whereas
• the next n lines of the input file contain the strings to be inserted.

• The first line contains two integers separated by a space character: the maximum path form the root to the leaves, and the internal path length, which is equal to the sum of the paths of all the tree nodes (note, that the path of the root is zero). These values are indications showing how well the tree is balanced.
• Then, n lines follow, where each line contains one string of characters. The characters allowed are "L" (for Left) and "R" (for Right) showing the path followed during the insertion of the corresponding string into the tree. Two special cases should be taken into consideration:
• If the inserted string is the first in the binary search tree, then the string "ROOT" should appear in the corresponding line.
• If the string already exists in the tree, then the string "EXISTS" should appear in the output.

Sample input:

7
door
ace
ace
external
extension
cat
flight

Sample output:

2 8
ROOT
L
EXISTS
R
RL
LR
RR