Question

In Java

For this assignment you will implement two methods, find() and replace() relating to Binary Search Trees. These methods are both to be recursive functions. The signatures for those functions must be:

 /* This method takes a tree node and a key as an argument and returns the tree node if the key is found and returns null if the key is not found. */ 
BST find(BST T, char key)

/* This method takes a tree node and a key as an argument and inserts the tree node if the key is already in the tree it does not insert the node. It returns the new tree. */
BST insert(BST T, char key)

Also, for this assignment you are to implement the preOrder(), inOrder(), and postOrder() tree traversal methods. These methods are also to be recursive functions.

All five of these methods are detailed and discussed in the lecture notes and videos. You are allowed to use the pseudo-code and any associated code described in the lecture and videos. However, you are not required for any of it.

The input for this program will be from the keyboard and accept single-character keys, labeled 'A' - 'Z'.

Programming Notes & Rules:

1. You can not delete any code in the BST class. But you can add code to the BST class if you wish.
2. All five methods must be recursive. Zero credit will be given for any non-recursive method even if it works correctly.
3. Do not assume any maximum length for any input string.
4. You need not test for the null or empty string ("") case,
5. You are not allowed to add any arrays or ArrayLists or any Java built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues, Deques, Trees, Graphs, Heaps, etc. Or add any class that inherits any of those ADTs.
6. For your node and list class, you can use the code that was used in the book, video, and lecture notes related to the node and lists class examples.
7. You are not allowed to use Java Generics.
8. If hard-coding detected in any part of your solution your score will be zero for the whole assignment.

Starter Code:

import java.util.Scanner;  // Import the Scanner class

public class BST {
  
  public char key;
  public BST  left;
  public BST  right;

  public BST(char c) {
    key   = c;
    left  = null;
    right = null;
  }
  
  public static BST find(BST T, char key) {
  // put your solution here
  }

  public static BST insert(BST T, char key) {
  //  put your solution here
  }
    
  public static void preOrder(BST T) {
  //  put your solution here
  }
  
  public static void inOrder(BST T) {
  //  put your solution here 
  }
  
  public static void postOrder(BST T) {
  //  put your solution here
  }
  
  public static void main(String[] args) {
     Scanner input = new Scanner(System.in);
     BST t = null;
     String stream = input.nextLine();
     for (int i = 0; i < stream.length(); i++)
       t = insert(t, stream.charAt(i));
     System.out.print("Preorder: ");
     preOrder(t);
     System.out.println();
     System.out.print("Inorder: ");
     inOrder(t);
     System.out.println();
     System.out.print("Postorder: ");
     postOrder(t);
     System.out.println();
     System.out.println("Enter a character to search for: ");
     char c = input.nextLine().charAt(0);
     if (find(t, c) == null)
       System.out.println("The character " + "'" + c + "' was not found.");
     else
       System.out.println("The character " + "'" + c + "' was found.");
   }

Answer 1

WHOLE CODE WITH IMPLEMENTED ABOVE METHODS :

import java.util.Scanner;  // Import the Scanner class

public class BST {

   public char key;
   public BST  left;
   public BST  right;

   public BST(char c) {
      key   = c;
      left  = null;
      right = null;
   }


   public static BST find(BST T, char key) {

      if(T==null)
         return null;

      if(T.key==key)
         return T;

      else if(key>T.key){
         return find(T.right,key);
      }

      else{
         return find(T.left,key);
      }

   }


   public static BST insert(BST T, char key) {

      if(T==null){
         BST newNode = new BST(key);
         return newNode;
      }

      if(T.key>=key){
         T.left = insert(T.left,key);
      }

      else{
         T.right=insert(T.right,key);
      }

      return T;
   }


   public static void preOrder(BST T) {
      if(T==null)
         return;

      System.out.print(T.key+" ");
      preOrder(T.left);
      preOrder(T.right);
   }


   public static void inOrder(BST T) {
      if(T==null)
         return;

      preOrder(T.left);
      System.out.print(T.key+" ");
      preOrder(T.right);

   }


   public static void postOrder(BST T) {
      if(T==null)
         return;

      preOrder(T.left);
      preOrder(T.right);
      System.out.print(T.key+" ");

   }


   public static void main(String[] args) {
      Scanner input = new Scanner(System.in);
      BST t = null;
      String stream = input.nextLine();
      for (int i = 0; i < stream.length(); i++)
         t = insert(t, stream.charAt(i));
      System.out.print("Preorder: ");
      preOrder(t);
      System.out.println();
      System.out.print("Inorder: ");
      inOrder(t);
      System.out.println();
      System.out.print("Postorder: ");
      postOrder(t);
      System.out.println();
      System.out.println("Enter a character to search for: ");
      char c = input.nextLine().charAt(0);
      if (find(t, c) == null)
         System.out.println("The character " + "'" + c + "' was not found.");
      else
         System.out.println("The character " + "'" + c + "' was found.");
   }



}

EXAMPLE :