Implement two methods, find() andreplace() relating to Binary Search Trees. Both ofthese methods must be recursive functions. The signatures for thefunctions 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 traversalmethods. These methods must also be recursive functions. The inputfor this program will be from the keyboard and acceptsingle-character keys, labeled 'A' - 'Z'.

Rules:

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

2) All 5 methods MUST be RECURSIVE. No credit is given if amethod 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 anyJava built-in (ADTs), such as Lists, Sets, Maps, Stacks, Queues,Deques, Trees, Graphs, Heaps, etc. or add any class that inheritsany 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 notfound.\");
else
System.out.println(\"The character \" + \"'\" + c + \"' wasfound.\");
}