# Practice with Recursion

import cs125.trees.BinaryTree;
int treeDepth(BinaryTree tree) {
return 0;
}
assert treeDepth(new BinaryTree<Integer>(0, 1, 2)) == 1;

Guess what? In this lesson we’ll be doing more practice with binary trees! And recursion! What could be more fun?

## Warm Up Debugging ChallengeWarm Up Debugging Challenge

Let’s warm up with another debugging challenge!

Create a public class `BinaryTreeCounter` that provides a single class method named `countEqualToEitherChild` that accepts a single `BinaryTree` and counts the number of nodes in the tree where the value at that node is equal to either the value at its right child or the value at its left child. Keep in mind that not every node has a right or left child, so you'll need to check for `null` carefully. (Or use `try-catch`!) However, you can assume that all of the values in the tree are non-null.

For reference, `cs125.trees.BinaryTree` has the following public properties:

## Tree DepthTree Depth

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.)

// Tree Depth ## Tree Node CountTree Node Count

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 this lesson’s homework problem—which is a tricky one!

// Tree Child Count ## Binary Search TreeBinary Search Tree

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;
for (int i = 1; i < values.length; i++) {
}
}
private void add(Object newValue) {
if (random.nextBoolean()) {
if (right == null) {
right = new BinaryTree(newValue);
} else { ## Practice: Binary Tree Search Path

Created By: learncs.online Staff / Version: 2020.11.0

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:

• If you reach an empty tree, you can return `false`, since an empty tree does not contain the value
• Otherwise, if this node contains the value, add yourself to the list, stop recursing, and return `true`.
• Otherwise, first search your right subtree. If that succeeds, then this node is also part of the path and should be added. If not, try the left subtree.
• If neither the right nor left subtree contains the node, you should return false and not modify the list, since this node is not on the path to the desired node.

Good luck and have fun!

import cs125.trees.BinaryTree;
import java.util.ArrayList;
import java.util.List;
public class BinaryTreePath {
public static List<Object> pathToValue(BinaryTree<Object> tree, Object value) {
List<Object> path = new ArrayList<>();
if (pathToValue(tree, value, path)) {
return path;
} else {
return null;
}
}
private static boolean pathToValue(BinaryTree<Object> tree, Object value, List<Object> path) {
return false;
}
}

## Homework: BinaryTree to Map

Created By: learncs.online Staff / Version: 2021.4.0

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.

For reference, `cs125.trees.BinaryTree` has the following public properties:

import cs125.trees.BinaryTree;
import java.util.Map;
public class BinaryTreeToMap {
public static Map<Object, Integer> toMap(BinaryTree<?> tree) {
// Check for null
// Create your map
// Call the helper method to populate the map
// Return the map
return null;
}
// Helper method
private static void toMap(BinaryTree<?> tree, Map<Object, Integer> values) {}
}

## More Practice

Need more practice? Head over to the practice page.