First Hellenic Internet Programming Contest
30 November 1996

Problem 3 - 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 file INPUT3.TXT, 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.

Example

• Input
  7
  door
  ace
  ace
  external
  extension
  cat
  flight
  
• Output
  2 8
  ROOT
  L
  EXISTS
  R
  RL
  LR
  RR
  

In order to get the ASCII files of the problem click here.