Question

Implement two methods, find() and replace() relating to Binary Search Trees. Both of these methods must be recursive functions. The signatures for the 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. */
BST insert(BST T, char key)

You will also implement the preOrder(), inOrder(), and postOrder() tree traversal methods. These methods must also be recursive functions. The input for this program will be from the keyboard and accept single-character keys, labeled 'A' - 'Z'.

Rules:

1) You cannot delete any code in the BST class, adding code is okay.

2) All 5 methods MUST be RECURSIVE. No credit is given if a method is not recursive, even if it works correctly.

3) Do not assume any maximum length for any input string.

4) Do not need to test for an empty string or null 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) The use of Java Generics is also not allowed.

Starter code which must be used:

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

Java 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;
    }

    /**
     *
     * @param T BST
     * @param key key to find
     * @return The BST node if found. Otherwise null
     */
    public static BST find(BST T, char key) {
        if (T==null || T.key==key)
            return T;

        // key is greater than T's key
        if (T.key > key)
            return find(T.left, key);

        // key is less than T's key
        return find(T.right, key);
    }

    /**
     *
     * @param T BST to insert the key into
     * @param key The key to be insertes
     * @return BST after insertion
     */
    public static BST insert(BST T, char key) {
        // Create and insert a new node
        if (T == null) {
            T = new BST(key);
            return T;
        }

        // if key is already present don't insert and return unchanged pointer
        if(T.key == key)
            return T;

        // Otherwise, recur down the tree
        if (key < T.key)
            T.left = insert(T.left, key);
        else if (key > T.key)
            T.right = insert(T.right, key);

        // return the unchanged pointer
        return T;
    }

    /**
     * Preorder traversal of the BST
     *
     * @param T BST
     */
    public static void preOrder(BST T) {
        if(T==null)
            return;
        System.out.print(T.key+" ");
        preOrder(T.left);
        preOrder(T.right);
    }

    /**
     * Inorder traversal of the BST
     *
     * @param T BST
     */
    public static void inOrder(BST T) {
        if(T==null)
            return;
        inOrder(T.left);
        System.out.print(T.key+" ");
        inOrder(T.right);
    }

    /**
     * Postorder traversal of the BST
     *
     * @param T BST
     */
    public static void postOrder(BST T) {
        if(T==null)
            return;
        postOrder(T.left);
        postOrder(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.");
    }
}

Output: