# (Solved) : Create Binary Search Tree Bst Contains First Million Prime Numbers Reading Data Output Max Q35300494 . . .

Create binary search tree (BST) that contains the first millionprime numbers. After you are reading in the data, output themaximum and average depth of the BST. Allow the user to enter anumber 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 primenumber 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

The nearest prime number less than your number is 23

The nearest prime number greater than your number is 29

My program so far is

package tree;

import java.util.*;

import java.io.*;

public class Tree {

static int MaxDepth =0, CurrentDepth = 0, SumCurrentDepth = 0,AverageDepth = 0;

public staticvoid main(String[] args) throwsIOException

{

File file = new File(“primes4.txt”);

Scanner infile = new Scanner(file);

Node Root = new Node(); //create root

Root.Data = infile.nextInt();

{

CurrentDepth = 0;

Insert (Root, infile.nextInt());

SumCurrentDepth += CurrentDepth;

if (CurrentDepth >MaxDepth)

MaxDepth = CurrentDepth;

}

System.out.println(Root.Left.Right.Data);

System.out.println(“Maximum Depth ofTree = ” + MaxDepth);

System.out.println(“Average Depth ofTree = ” + AverageDepth);

int N = 25;

if (!Locate(Root, N));

{

//print nearest number less than and greater than

int NearestLess = N;

while (!Locate(Root, NearestLess))

{

NearestLess–;

}

int NearestGreater = N;

while (!Locate(Root,NearestGreater))

{

NearestGreater++;

}

System.out.println(“Nearest numberless than yours is ” + NearestLess);

System.out.println(“Nearest numbergreater than your number is ” + NearestGreater);

}

}

static boolean Locate(NodeTheNode, int TheData)

{

if (TheNode == null)

return false;

if (TheNode.Data == TheData)

return true;

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

returnLocate(TheNode.Left,TheData);

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

returnLocate(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 adefault return

}

static void Insert(NodeTheNode, int NewData)

{

CurrentDepth++;

if (TheNode.Data > NewData &&TheNode.Left == null) //Left is null – add newnode on left

{

Node T = new Node();

T.Data = NewData;

TheNode.Left = T;

}

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

{

Node T = new Node();

T.Data = NewData;

TheNode.Right = T;

}

else if (TheNode.Data >NewData && TheNode.Left != null) //Leftisn’t null – recurse to left

Insert(TheNode.Left, NewData);

else if (TheNode.Data <NewData && TheNode.Right != null) //Rightisn’t null – recurse to right

Insert(TheNode.Right, NewData);

}

}

class Node

{

int Data;

Node Left, Right;

}