binary search tree in java plz solve all the Qs (methods) and read the Qs carefu
ID: 3834355 • Letter: B
Question
binary search tree in java
plz solve all the Qs (methods) and read the Qs carefully
i included the class BST node , class BST(to write all the methods )and test (main methode)
HERE R THE Qs
1. A method that generate a binary search tree (BST) where the number of nodes and the range of the values are
from a file. ---> i didn't know how to do this so i made the input from the main
2. A recursive method to find the largest value in a BST
3. A method to find and return the smallest value in a BST.
4. A method to search for a given value V in a BST.
5. A method to count the number of ancestors of a given value V
6. A method to count the number of comparisons to decide whether a given value V is in a BST.
7. A method to count the number of leaf nodes in BST
8. A method to count the number of nodes that contain even numbers in a BST
CLASSBST NODE
package bst;
public class BSTclassNode {
private Comparable value;
private BSTclassNode left;
private BSTclassNode right;
public BSTclassNode(Comparable value) {
this.value = value;
left = null;
right = null;
}
public boolean add(Comparable value) {
if (value.compareTo(this.value) == 0) {
return false;
} else if (value.compareTo(this.value) < 0) {
if (left == null) {
left = new BSTclassNode(value);
return true;
} else {
return left.add(value);
}
} else if (value.compareTo(this.value) > 0) {
if (right == null) {
right = new BSTclassNode(value);
return true;
} else {
return right.add(value);
}
}
return false;
}
public boolean search(Comparable value) {
if (value.compareTo(this.value) == 0) {
return true;
} else if (value.compareTo(this.value) < 0) {
if (left == null) {
return false;
} else {
return left.search(value);
}
} else if (value.compareTo(this.value) > 0) {
if (right == null) {
return false;
} else {
return right.search(value);
}
}
return false;
}
public void printInOrder(BSTclassNode node) {
if (node == null) {
return;
}
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
public void postOrder(BSTclassNode node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.value);
}
public void preOrder(BSTclassNode node) {
if (node == null) {
return;
}
System.out.println(node.value);
preOrder(node.left);
preOrder(node.right);
}
public int countNodes(BSTclassNode node) {
int count = 0;
if (node == null) {
return 0;
}
count += countNodes(node.left);
count++;
count += countNodes(node.right);
return count;
}
// public int getMax(BSTclassNode node) {
// if (node.right == null) {
// return 0;
// }
// return Math.max(0, getMax(node.right));
// }
}
CLASS BST( TO WRITE THE METHODS)
package bst;
public class BinarySearchTree {
private BSTclassNode root;
private BSTclassNode right;
public BinarySearchTree() {
root = null;
}
public boolean add(Comparable value) {
if (root == null) {
root = new BSTclassNode(value);
return true;
} else {
return root.add(value);
}
}
public boolean search(Comparable value) {
if (root == null) {
return false;
} else {
return root.search(value);
}
}
public void printInOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public void postOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public void preOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public int countNodes() {
if (root == null) {
return 0;
} else {
return root.countNodes(root);
}
}
// public int getMax() {
// if (right == null) {
// return 0;
// } else {
// return right.getMax(right);
// }}
}
MAIN METHOD
package bst;
public class TestBST {
public static void main(String[] args) {
BinarySearchTree myBST = new BinarySearchTree();
myBST.add(10);
myBST.add(5);
myBST.add(15);
myBST.add(3);
myBST.add(13);
myBST.add(1);
myBST.add(20);
System.out.println("printing post order");
myBST.postOrder();
System.out.println("printing pre order");
myBST.preOrder();
System.out.println("printing in order");
myBST.printInOrder();
System.out.println("The number of nodes is " + myBST.countNodes());
System.out.println("Searching for 13 " + myBST.search(13));
System.out.println("Searching for 8 " + myBST.search(8));
// System.out.println("getting max number in BST " +myBST.getMax());
}
}
Explanation / Answer
Below are the updated files for your requirement. Sample input file and output is shown. Please dont forget to rate the answer if it helped. Thank you very much.
BSTclassNode.java
package bst;
public class BSTclassNode {
private Comparable value;
private BSTclassNode left;
private BSTclassNode right;
public BSTclassNode(Comparable value) {
this.value = value;
left = null;
right = null;
}
public boolean add(Comparable value) {
if (value.compareTo(this.value) == 0) {
return false;
} else if (value.compareTo(this.value) < 0) {
if (left == null) {
left = new BSTclassNode(value);
return true;
} else {
return left.add(value);
}
} else if (value.compareTo(this.value) > 0) {
if (right == null) {
right = new BSTclassNode(value);
return true;
} else {
return right.add(value);
}
}
return false;
}
public boolean search(Comparable value) {
if (value.compareTo(this.value) == 0) {
return true;
} else if (value.compareTo(this.value) < 0) {
if (left == null) {
return false;
} else {
return left.search(value);
}
} else if (value.compareTo(this.value) > 0) {
if (right == null) {
return false;
} else {
return right.search(value);
}
}
return false;
}
public void printInOrder(BSTclassNode node) {
if (node == null) {
return;
}
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
public void postOrder(BSTclassNode node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
System.out.println(node.value);
}
public void preOrder(BSTclassNode node) {
if (node == null) {
return;
}
System.out.println(node.value);
preOrder(node.left);
preOrder(node.right);
}
public int countNodes(BSTclassNode node) {
int count = 0;
if (node == null) {
return 0;
}
count += countNodes(node.left);
count++;
count += countNodes(node.right);
return count;
}
public Comparable getMax() {
if (right == null) {
return value;
}
else
return right.getMax();
}
public Comparable getMin() {
if (left == null) {
return value;
}
else
return left.getMin();
}
public int countAncestors(Comparable v, int currentAncestor)
{
if(value.compareTo(v)==0)
{
return currentAncestor;
}
else
{
if(v.compareTo(value) < 0 && left!=null)
{
return left.countAncestors(v, currentAncestor+1);
}
else if(v.compareTo(value) > 0 && right !=null)
{
return right.countAncestors(v, currentAncestor+1);
}
else
return 0;
}
}
public int countLeaves()
{
if(left == null && right==null)
return 1;
else
{
int count = 0;
if(left!=null)
count+= left.countLeaves();
if(right!=null)
count+= right.countLeaves();
return count;
}
}
public int countEven()
{
int count= 0;
if(value instanceof Integer && ((Integer)value) %2 == 0)
count++;
if(left!=null)
count += left.countEven();
if(right!=null)
count += right.countEven();
return count;
}
public int countComparisons(Comparable v)
{
int cmp = v.compareTo(value);
if(cmp == 0)
return 1;
else
{
if(cmp < 0 && left!=null)
return 1+left.countComparisons(v);
else if(cmp > 0 && right != null)
return 1+right.countComparisons(v);
else
return 1;
}
}
}
BinarySearchTree.java
package bst;
public class BinarySearchTree {
private BSTclassNode root;
private BSTclassNode right;
public BinarySearchTree() {
root = null;
}
public boolean add(Comparable value) {
if (root == null) {
root = new BSTclassNode(value);
return true;
} else {
return root.add(value);
}
}
public boolean search(Comparable value) {
if (root == null) {
return false;
} else {
return root.search(value);
}
}
public void printInOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public void postOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public void preOrder() {
if (root == null) {
return;
} else {
root.printInOrder(root);
}
}
public int countNodes() {
if (root == null) {
return 0;
} else {
return root.countNodes(root);
}
}
public Comparable getMax() {
if (root == null) {
return 0;
} else {
return root.getMax();
}
}
public Comparable getMin() {
if (root == null) {
return 0;
} else {
return root.getMin();
}
}
public int countAncestors(Comparable v)
{
if(root== null)
return 0;
else
return root.countAncestors(v,0);
}
public int countLeaves()
{
if(root == null)
return 0;
else
return root.countLeaves();
}
public int countEven()
{
if(root == null)
return 0;
else
return root.countEven();
}
public int countComparisons(Comparable v)
{
if(root ==null)
return 0;
else
{
return root.countComparisons(v);
}
}
}
TestBST.java
package bst;
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Random;
import java.util.Scanner;
public class TestBST {
/*method reads a file containing the number of nodes and the range of the values
The assumed format for the file is
<count> <m> <n>
where <count> is hte number of nodes
and <m> <n> specifies the lower and upper end of the range.
Number in this range are randomly generated as many as <count> and added to BST.
*/
public static void readFile(String filename,BinarySearchTree bst)
{
try {
Scanner scanner = new Scanner(new File(filename));
int count, m, n, diff, elem;
count = scanner.nextInt();
m = scanner.nextInt();
n = scanner.nextInt();
diff = n -m;
Random random = new Random();
System.out.println("Adding "+count+" elements in the range of "+m+" - "+n);
//randomly generate count number of eleemntes and add to BST
int i =0;
while(i<count)
{
elem = m + random.nextInt(diff);
if(bst.search(elem) == true) //check if the number is already in bst , if so generate another
continue;
System.out.println("Adding "+elem);
bst.add(elem);
i++;
}
System.out.println("The BST in inorder after adding numbers as specified in file is ");
bst.printInOrder();
} catch (FileNotFoundException e) {
System.out.println("File not found "+filename);
System.out.println("No nodes were added to BST");
}
}
public static void main(String[] args) {
String filename="bstvalues.txt"; //filename containing number of nodes and range
BinarySearchTree myBST = new BinarySearchTree();
readFile(filename, myBST);
System.out.println("printing post order");
myBST.postOrder();
System.out.println("printing pre order");
myBST.preOrder();
System.out.println("printing in order");
myBST.printInOrder();
System.out.println("The number of nodes is " + myBST.countNodes());
System.out.println("Searching for 13 " + myBST.search(13));
System.out.println("Searching for 8 " + myBST.search(8));
System.out.println("getting max number in BST " +myBST.getMax());
System.out.println("getting min number in BST " +myBST.getMin());
System.out.println("The number of leaves is "+myBST.countLeaves());
Comparable num = myBST.getMax();
System.out.println("The number of ancestors for "+num+" is "+myBST.countAncestors(num));
System.out.println("The number of even nodes in the tree are : "+myBST.countEven());
System.out.println("The number of comparsions for "+num+" is "+myBST.countComparisons(num));
}
}
Input file first number 5 is the number of elements to add to BST. 1 is the starting of the range and 10 is the ending of range. So 5 numbers in the range 1-10 are added to BST.
sample input file bstvalues.txt
5 1 10
output
Adding 5 elements in the range of 1 - 10
Adding 6
Adding 7
Adding 3
Adding 9
Adding 8
The BST in inorder after adding numbers as specified in file is
3
6
7
8
9
printing post order
3
6
7
8
9
printing pre order
3
6
7
8
9
printing in order
3
6
7
8
9
The number of nodes is 5
Searching for 13 false
Searching for 8 true
getting max number in BST 9
getting min number in BST 3
The number of leaves is 2
The number of ancestors for 9 is 2
The number of even nodes in the tree are : 2
The number of comparsions for 9 is 3
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.