Consider the following Java method belonging to the Tree class. It compiles corr
ID: 3582350 • Letter: C
Question
Consider the following Java method belonging to the Tree class. It compiles correctly; however, it does not function as described in the comments. What is wrong? How would you fix it?//Recursively searches the tree starting at current for the target private boolean search (int target, TreeNode current) {if (current == null) return false; else if (current. getDatum() == target) return true; else if (current.getDatum() > target) return search(target, current.getRight()) else return search (target, current.getLeft());}Explanation / Answer
A binary search Tree structure will be, for a given node all the elements less than the root will be to the left of the tree, and all the elements greater than the root will be to the right. Therefore, if the given tree is BST the logic the last two steps are going the exact opposite way, and therefore needs a modification:
private boolean search(int target, TreeNode current)
{
if(current == null)
return false;
else if(current.getDatum() == target)
return true;
else if(current.getDatum() > target)
return search(target, current.getLeft());
else
return search(target, current.getRight());
}
Whereas, if the tree is not binary, there is no guarantee that the nodes will follow this order, i.e., the lesser values to the left, and greater values to the right. So, the search should go on both the ways like this:
private boolean search(int target, TreeNode current)
{
if(current == null)
return false;
else if(current.getDatum() == target)
return true;
else
return search(target, current.getLeft()) || search(target, current.getRight());
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.