Guess what? In this lesson we’ll be doing more practice with binary trees! And recursion! What could be more fun?
But, would we want to miss out on another 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 this lesson’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.
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 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
null if the tree does not contain the passed
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
Our wrapper method initializes the list properly and then calls a private helper method which performs the
The helper should return
true if the tree contains the value, and if it does also manipulate the list
If the tree does not contain the value it should return
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:
false, since an empty tree does not contain the value
Good luck and have fun!
Create a public class
BinaryTreeToMap that provides a single
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
null you should throw an
You will need to import
cs125.trees.BinaryTree, as well as
Map and a
Map implementation (probably
We've provided some code to get you started.
cs125.trees.BinaryTree has the following public properties:
Need more practice? Head over to the practice page.