Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
But, could it be Friday without a debugging challenge? No way!
As a warm up let’s write a recursive function to determine the depth or height of a tree. As a reminder, the depth is defined as the distance from the root node to the farthest leaf node. (The depth is not defined for a empty tree, since it has no root.)
Next, let’s look at an example of a recursive function that passes another data structure around. We’ll write a recursive method that returns an array with counts of the number of nodes that have zero, one, or two children. This will also prepare you for today’s homework problem—which is a tricky one!
Finally, let’s look again at the problem of locating a node in a binary tree. We’ll start with code from our previous answer, redesign it to be more efficient, and then analyze the performance of our new approach.
import java.util.Random;
// Binary Search Tree
public class BinaryTree {
private Object value;
private BinaryTree right;
private BinaryTree left;
private Random random = new Random();
public BinaryTree(Object setValue) {
value = setValue;
}
public BinaryTree(Object[] values) {
assert values.length > 0;
value = values[0];
for (int i = 1; i < values.length; i++) {
add(values[i]);
}
}
private void add(Object newValue) {
if (random.nextBoolean()) {
if (right == null) {
right = new BinaryTree(newValue);
} else {
right.add(newValue);
}
} else {
if (left == null) {
left = new BinaryTree(newValue);
} else {
left.add(newValue);
}
}
}
public boolean findValue(Object lookingFor) {
return false;
}
}
BinaryTree tree = new BinaryTree(new String[] {“you”, “are”, “not”, “alone”});
assert tree.findValue(“not”);
Let’s continue exploring recursion on binary trees. However, this problem takes a significant step forward in difficulty, so be prepared!
We’ve provided a public class BinaryTreePath with a single class method pathToValue. pathToValue accepts a BinaryTree<Object> as its first parameter and an Object as its second. It returns a List<Object> containing all the values in the tree on the way to the first node with a value equal to the passed Object, or null if the tree does not contain the passed Object. We’ve handled this case already for you in the starter code. However, you should fix pathToValue so that it throws an IllegalArgumentException if either the passed tree or the passed value is null.
Our wrapper method initializes the list properly and then calls a private helper method which performs the recursion. The helper should return true if the tree contains the value, and if it does also manipulate the list properly. If the tree does not contain the value it should return false. You will want to use add(int index, Object value) to add values to the front of the list as you work your way through the tree.
This problem is hard! Here’s an outline of a solution to help get you started:
Good luck and have fun!
Create a public class BinaryTreeToMap that provides a single static method toMap. toMap accepts a BinaryTree<?> and returns a Map<Object, Integer> mapping the values in the tree to the count of the times that the value appears.
Our suggestion is to have toMap create the map and then call a private recursive helper method to populate it. If the tree passed to toMap is null you should throw an IllegalArgumentException. You will need to import cs125.trees.BinaryTree, as well as Map and a Map implementation (probably HashMap) from java.util. We’ve provided some code to get you started.