Create binary search tree (BST) that contains the first million prime numbers. After you are reading in the data, output the maximum and average depth of the BST. Allow the user to enter a number to see whether or not it is prime. If the number is found, output the depth at which it was found. If the number isn't found, output the nearest prime number greater than and the nearest prime number less than the user's number.

EXAMPLE OUTPUT Creating Binary Tree from 1000000 prime numbers... The maximum depth of the tree is? The average depth of the tree is ? Enter a number to see if it's in the tree: 25 Your number was not found. The nearest prime number less than your number is 23 The nearest prime number greater than your number is 29

Below is the code that needs to be fixed.

import java.util.Scanner;

import java.io.*;

import java.util.*;

public class BinaryTree

{

static int Depth;

public static void main(String[] args) throws IOException

{

File file = new File("primes4.txt");

Scanner infile = new Scanner(file);

int Count = 1;

int MaxDepth = 0;

Node Root = new Node();

Root.Data = infile.nextInt();

while (infile.hasNextInt())

{

Count++;

Depth = 0;

Insert(Root, infile.nextInt());

if(Depth > MaxDepth)

MaxDepth = Depth;

}

System.out.println("Finished reading " + Count + " Prime numbers ");

System.out.println("Maximum Depth = " + MaxDepth);

}

static boolean Locate(Node TheNode, int TheData)

{

if (TheNode == null)

return false;

if (TheNode.Data == TheData)

return true;

else if (TheNode.Data > TheData) // traverse tree to the left

return Locate(TheNode.Left,TheData);

else if (TheNode.Data < TheData) // traverse tree to the right

return Locate(TheNode.Right,TheData);

else if (TheNode.Data > TheData && TheNode.Left == null)

return false;

else if (TheNode.Data < TheData && TheNode.Right == null)

return false;

return false; // Java needs a default return

}

static void Insert(Node TheNode, int NewData)

{

Depth++;

if (TheNode.Data > NewData && TheNode.Left == null) // Left is null - add new node on left

{

Node T = new Node();

T.Data = NewData;

TheNode.Left = T;

}

else if (TheNode.Data < NewData && TheNode.Right == null) // Right is null - add new node on right

{

Node T = new Node();

T.Data = NewData;

TheNode.Right = T;

}

else if (TheNode.Data > NewData && TheNode.Left != null) // Left isn't null - recurse to left

Insert(TheNode.Left, NewData);

else if (TheNode.Data < NewData && TheNode.Right != null) // Right isn't null - recurse to right

Insert(TheNode.Right, NewData);

}

}

class Node

{

int Data;

Node Left, Right;

Node()

{

Left = null;

Right = null;

}

}

public void run()

{

int count = 0;

Node root = new Node(2);

System.out.println("Building the tree having root value " + root.value);

for (int i = 3; count < 100; i++)

{

if (isPrime(i) == true)

{

count += 1;

insert(root, i);

}

}

System.out.println("Traversing the tree in order");

printTreeInOrder(root);

Scanner s = new Scanner(System.in);

System.out.println("Enter a number to check if it is prime or not: ");

int num = s.nextInt();

if (isPrime(num) == true)

{

System.out.println(num + " is Prime number");

}

else

{

int Lower = num;

while (!isPrime(Lower))

Lower--;

System.out.println("Nearest prime number lesser than " + num + " is " + Lower);

for (int i = num + 1;; i++)

{

if (isPrime(i) == true)

{

System.out.println("Nearest prime number greater than " + num + " is " + i);

break;

}

}

}

}

public void insert(Node node, int value)

{

if (value < node.value)

{

if (node.left != null)

{

insert(node.left, value);

}

else

{

System.out.println("Inserted " + value + " to the left of " + node.value);

node.left = new Node(value);

}

}

else if (value > node.value)

{

if (node.right != null)

{

insert(node.right, value);

}

else

{

System.out.println("Inserted " + value + " to the right of " + node.value);

node.right = new Node(value);

}

}

}

public void printTreeInOrder(Node node)

{

if (node != null)

{

printTreeInOrder(node.left);

System.out.println(node.value);

printTreeInOrder(node.right);

}

}

public boolean isPrime(int n)

{

for (int i = 2; i <= n / 2; i++)

{

if (n % i == 0)

{

return false;

}

}

return true;

}

}