/******************************************************************\
 -- BinTree --
 Trees can be used for a very simple application -
 store a list of names (or other strings) in a BINARY SEARCH TREE,
 then search the tree to find a name.  This is very fast - O(log N)-
 and is suitable for performing a spell-check by looking up word in a dictionary
 (1) Does the DISPLAY method work correctly?
 (2) What kind of TRAVERSAL is performed by DISPLAY?
 (3) Find a case where SEARCH works correctly.
 (4) Find a case where SEARCH returns the wrong answer.
 (5) Find a case where SEARCH returns no answer at all.
 (6) Change the TREE to contain the following words:
     "public" , "class" , "static" , "void" , "main" , "int" , "while"
     You must put the words into data[] in THAT order.
     Then change the left and right pointers to make a proper
     binary-search-tree.  The DISPLAY method should still work properly.
 (7) FIX the search procedure.
 (8) Change the SEARCH method so that it returns an int instead
     of returning a boolean.  If a word is found, it should return
     the POSITION of the word in the data[] array.  If the word
     is NOT FOUND, it should return zero (0).
 (9) EXPLAIN how a new method could be written to ADD new words
     to the data tree.  Don't write the method, just explain it
     in English.
\******************************************************************/

public class BinTree
{ public static void main(String[] args)
  { new BinTree();}

  int root = 4;
  String[] data  = {"","Compaq","HP","King","Mac","PC","Sun","Xeon"};
  int[]  left  = { 0 , 0 , 1 , 0 , 2 , 0 , 5 , 0 };
  int[]  right = { 0 , 0 , 3 , 0 , 6 , 0 , 7 , 0 };

  public BinTree()
  {  display(root);
     String target = "";
     do
     { target = input("What name do you want to find (or QUIT)?");
       boolean result = search(root,target);
       output(result + "");
     } while ( !target.equals("QUIT") ) ;
  }

  public void display(int here)
  { if (left[here] !=0)
    { display( left[here] ); }

    output( data[here] );

    if (right[here] != 0)
    { display( right[here] ); }
  }

  public boolean search(int here,String target)
  { if ( target.equals(data[here]) )
    { return true; }
    else if ( target.compareTo( data[here] ) < 0 )
    { return false; }
    else
    { search( right[here],target );
      return true;
    }

  }

//---- Write your program above -------
//---- Below are simple input and output methods ----

  static void output(String info)
  {  System.out.println(info);
  }

  static void output(double info)
  {  System.out.println(info);
  }

  static void output(long info)
  {  System.out.println(info);
  }

  static int inputInt(String Prompt)
  {  int result=0;
     try{result=Integer.valueOf(input(Prompt).trim()).intValue();}
     catch (Exception e){result = 0;}
     return result;
  }

  static double inputDouble(String Prompt)
  {  double result=0;
     try{result=Double.valueOf(input(Prompt).trim()).doubleValue();}
     catch (Exception e){result = 0;}
     return result;
  }

  static String input(String prompt)
  {  String inputLine = "";
     System.out.print(prompt);
     try
      {inputLine = (new java.io.BufferedReader(new java.io.InputStreamReader(System.in))).readLine();}
     catch (Exception e)
      { String err = e.toString();
        System.out.println(err);
      }
     return inputLine;
  }

}

/***
====== ANSWERS ======

(1) Yes, it works correctly
(2) Inorder (left-parent-right)
(3) Sun
(4) HP
(5) zzz
(6)
  int root = 1;

  String[] data  = {"","public","class","static","void","main","int","while"};
  int[]  left  =   { 0 ,  6    ,   0   ,   0    ,   3  ,  0   ,  2  , 0 };
  int[]  right =   { 0 ,  4    ,   0   ,   0    ,   7  ,  0   ,  5  , 0 };  

(7)
   Notice that each RECURSIVE call will return a value,
   and these values need to be returned further up the recursion tree.   
   That is :   search... is WRONG.  
   Write   :   RETURN search...

  public boolean search(int here,String target)
  { if ( target.equals(data[here]) )
    { return true; }
    else if ( target.compareTo( data[here] ) < 0 )
    {  if (left[here] == 0)
       {  return false; }
       else
       {
          return search( left[here],target);
       }   
    }
    else
    {  if (right[here] == 0)
       { return false; }
       else
       {
          return search( right[here],target );
       }   
    }
    
(8) Just change the return type to int:

       public int search(int here, String target)
       
    and then change return false to
    
       return 0;
       
(9) FIRST it must record the new data in the data[] array, making this LONGER.
    That is a problem in Java, so it would be better to start with a BIT array (say 1000).
    ADD is similar to the SEARCH method.  But it WANTS to continue
    until a 0 pointer is found.  Then, instead of returning 0 (or false),
    it needs to save a pointer in the left or right array.


***/