Today you are going to search through a binary search tree to find out if it con
ID: 3919778 • Letter: T
Question
Today you are going to search through a binary search tree to find out if it contains a specified value Details Download the ZIP files named FilesNeeded.zip for use in IntelliJ. When you are happy with your solution, upload the files into the src folder and run. You are going to finish off PoD.java to finish the findValue method Input The main method (already completed) creates a binary tree and passes a Comparable object to search for and the binary tree to search to the method findValue. Processing You are going to complete the details of findValue method. Details of each method and their expected parameters are described in the Javadoc comments preceding it. The method should return true if the value is found within the binary tree, and return false if not. Output Output will be handled by the main method based on the value you return. Examples Sample binary tree (created from samplelnput.in)Explanation / Answer
Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts. Thanks
// PoD.java
import java.util.*;
public class PoD {
// =============================================================================
/**
* Tries to find an object within the binary tree and returns true if found
* and false if not
*
* @param obj
* Comparable to search for in tree
* @param tree
* BinaryTree of interest
* @return boolean value true if object is found, false if not
* The below method works only for Binary Search Trees, and not for all binary trees
*/
public static boolean findValue(Comparable value, BinaryTree tree) {
if (tree.isEmpty()) {
//not found
return false;
}
//checking if the root node contains search value
if (tree.data().compareTo(value) == 0) {
//found
return true;
}
if(tree.data().compareTo(value)>0){
return findValue(value, tree.left());
}else{
return findValue(value, tree.right());
}
}
/**
* The below method works for all binary trees including binary search trees. Choose
* the method above or below as you needed.
*/
/*
public static boolean findValue(Comparable value, BinaryTree tree) {
if (tree.isEmpty()) {
//not found
return false;
}
//checking if the root node contains search value
if (tree.data().compareTo(value) == 0) {
//found
return true;
}
//checking left sub tree
if (findValue(value, tree.left())) {
return true;
}
//checking right subtree
if (findValue(value, tree.right())) {
return true;
}
//not found
return false;
}*/
// =============================================================================
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
Comparable value = in.next();
BinaryTree newTree = buildTree(in);
boolean foundItem = findValue(value, newTree);
if (foundItem) {
System.out.println("Found " + value);
} else {
System.out.println("Could not find " + value);
}
in.close();
System.out.print("END OF OUTPUT");
}
public static BinaryTree buildTree(Scanner in) {
String data = in.next();
BinaryTree left = null;
BinaryTree right = null;
if (data.equals("null")) {
return null;
}
if (!in.next().equals("(")) {
System.out.println("BAD INPUT: (L");
}
left = buildTree(in);
right = buildTree(in);
if (!in.next().equals(")")) {
System.out.println("BAD INPUT: R)");
}
return new BinaryTree(data, left, right);
}
}
/*OUTPUT*/
a
d ( b ( a ( null null ) c ( null null ) ) e ( null null ) )
Found a
END OF OUTPUT
x
d ( b ( a ( null null ) c ( null null ) ) e ( null null ) )
Could not find x
END OF OUTPUT
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.