#include <iostream.h>
#include <fstream>
#include <string>
using namespace std;

class Node
   {
      private:
         Node *smaller, *bigger;
      string theWord;
      int frequency;
      public:
         Node(string word)
         {
         smaller = 0;
         bigger = 0;
         theWord = word;
         frequency = 1;
         }

      void addWord(string word)
         {
         if(word == theWord)
            {
            frequency = frequency + 1;
            }
         else if(word < theWord)
            {
            if(smaller == 0)
               {
               smaller = new Node(word);
               }
            else
               {
               smaller->addWord(word);
               }
            }
         else if(word > theWord)
            {
            if(bigger == 0)
               {
               bigger = new Node(word);
               }
            else
               {
               bigger->addWord(word);
               }
            }
         }

      void print()
         {
         if(bigger != 0)
            bigger->print();
         cout << theWord << "   :   "<< frequency << endl;
         if(smaller != 0)
            smaller->print();
         }

      void printfirst()
         {
         if(smaller != 0)
            smaller->printfirst();
         else
            cout << theWord << "   :   "<< frequency << endl;
         }

      void printlast()
         {
         if(bigger != 0)
            bigger->printlast();
         else
            cout << theWord << "   :   "<< frequency << endl;
         }
   };

class Head
   {
      private:
      Node *tree;
      public:
         Head()
         {
         tree= 0;
         }

      void addWord(string word)
         {
         if(tree == 0)
            tree = new Node(word);
         else
            {
            tree->addWord(word);
            }
         }

      void print()
         {
         if(tree == 0)
            cout << "No data." << endl;
         else
            tree->print();
         }

      void printfirst()
         {
         if(tree == 0)
            cout << "No data." << endl;
         else
            tree->printfirst();
         }

      void printlast()
         {
         if(tree == 0)
            cout << "No data." << endl;
         else
            tree->printlast();
         }

   };


int main()
   {
   Head *h;
   h = new Head();
   string word;
   ifstream iFile("IDEN.txt");

   if(! iFile)
      {
      cout << "Error opening input file" << endl;
      return -1;
      }

   while(iFile >> word)
      {
      h->addWord(word);
      }

   cout << "The Alphabetically first word is: " ;
   h->printfirst();
   cout << "The Aphabetically last word is: ";
   h->printlast();
   cout << "The entire list: " << endl;
   cout << endl << endl;
   h->print();
   return 0;
   }