class Tree
 {
  /*                          APS 105 - Lab 8 - April 2001                     
*/
  /*                          Binary Search Tree Operations                    
*/
  /*                          Written by John Carter                           
*/          

  // This class contains methods that manipulate a binary search tree whose
nodes
  // contain strings in their info fields
  
  private Node root;
  
  public Tree()
   {
    // a basic constructor
    root = null;
   }
  
  public void printTree ()
   {
    // print the contents of a non-empty tree by calling the method
    // printTree in the inner Node class
    if (root != null)
      root.printTree();
   }
   
  public void insert (String s)
   {
    // insert a new node into an empty tree or call the method insert
    // in the inner Node class if the tree is not empty   
    if (root == null)
      root = new Node(s);
    else 
      root.insert(s);
   }
   
  public void convertToLowercase ()
   {
    // convert strings in a tree to lower case by calling the method
    // convertToLowercase in the inner Node class
    if (root != null)
      root.convertToLowercase();
   }
   
  public void printPairs (Tree other)
   {
    // find and print strings that are found in both the implicit 
    // tree and other by calling the method printPairs in the inner
    // Node class iff the implicit tree object is not empty
    if (root != null)
      root.printPairs(other);
   }
  
  void printIfMatchFound (String s)
   {
    // print the value of the string s iff the implicit tree object
    // has a node that contains s - for a non-empty tree, this is 
    // done using the method printIfMatchFound in the inner Node class
    if (root != null)
      root.printIfMatchFound(s);
   }
   
  class Node
   {
    // an inner class for the nodes of a tree
    
    String info;
    Node lLink;
    Node rLink;
   
    Node (String word)
     {
      // a simple constructor
      info = word;
      lLink = null;
      rLink = null;
     }
     
    void printTree ()
     {
      // print the nodes of a non-empty tree recursively, using an
      // inorder traversal of the tree
      if (lLink != null)
        lLink.printTree();
      System.out.println(info);
      if (rLink != null)
        rLink.printTree();        
     }
     
    void insert (String s)
     {
      // insert a new node in a non-empty binary search tree provided
      // that the string s is not already in the tree - the test of  
      // equality of strings ignores the case of the letters 
      String sLower = s.toLowerCase();
      String iLower = info.toLowerCase();
      System.out.println(sLower + " : " + iLower); 
      if (sLower.compareTo(iLower) < 0)
        if (lLink == null)
          lLink = new Node(s);
        else
          lLink.insert(s);
      if (sLower.compareTo(iLower) > 0)
        if (rLink == null)
          rLink = new Node(s);
        else
          rLink.insert(s);
     }
     
    void convertToLowercase ()
     {
      // convert all the strings in the nodes of a tree to lower
      // case letters
      info = info.toLowerCase();
      if (lLink != null)
        lLink.convertToLowercase();
      if (rLink != null)
        rLink.convertToLowercase();
     }
     
    void printPairs (Tree other)
     {
      // initiate the printing of pairs of values in two trees
      // by traversing the non-empty implicit tree object recursively
      // and calling the method printIfMatchFound to look for each string
      // in the tree other and print the string if a match is found
      if (lLink != null)
        lLink.printPairs(other);
      other.printIfMatchFound(info);
      if (rLink != null)
        rLink.printPairs(other);
     }
     
    void printIfMatchFound(String s)
     {
      // recursively search for s in the non-empty implicit tree
      // object, printing the string iff a match is found
      if (s.equals(info))
        System.out.println(s);
      else if (s.compareTo(info) < 0
               && lLink != null)
        lLink.printIfMatchFound(s);
      else if (s.compareTo(info) > 0
               && rLink != null)
        rLink.printIfMatchFound(s);
     }
   }
 }
class TreeTest
 {
  /*                            APS 105 - Lab 8 - April 2001                      
*/
  /*                            Binary Search Tree Operations                     
*/
  /*                            Written by John Carter                            
*/
  
  public static void main (String[] args)
   {
    // This program uses the methods of the Tree class to first read words into
one of
    // two binary search trees - one containing words that begin with an
uppercase
    // letter and one that contains words that begin with a lowercase letter. 
Input is
    // terminated by the string "ZZZ".
    // Once all words have been read, the contents of the two trees are printed
in
    // lexicographic order, any uppercase letters in the strings of either tree
are
    // converted to lowercase letters, the contents of the altered trees are
printed,
    // and any stings appearing in both trees are found and printed.
     
    Tree ucTree = new Tree();
    Tree lcTree = new Tree();
    
    // get input and insert each word in appropriate tree
    System.out.println("Enter a word - ZZZ to stop");
    String next = Stdin.getString();
    while (!next.equals("ZZZ"))
     {
      char firstChar = next.charAt(0);
      if (firstChar >= 'A' && firstChar <= 'Z')
        ucTree.insert(next);
      else
        lcTree.insert(next);
      System.out.println("Next word - ZZZ to stop");
      next = Stdin.getString();
     }
     
    // print both trees
    ucTree.printTree();
    System.out.println();
    lcTree.printTree();
    System.out.println();
    
    // convert all letters to lower case and print altered trees
    ucTree.convertToLowercase();
    lcTree.convertToLowercase();
    ucTree.printTree();
    System.out.println();
    lcTree.printTree();
    System.out.println();
    
    // find and print words that are in both trees
    ucTree.printPairs(lcTree);
   }
 }