Guess what? In this lesson we’ll be doing more practice with binary trees! And recursion! What could be more fun?
Let’s warm up with another debugging challenge!
Create a 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
is defined like this:
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 method pathToValue
that accepts a BinaryTree<Any>
as its first parameter
and an Any
as its second.
It returns a List<Any>
containing all the values in the tree on the way to the first node with a
value equal to the passed Any
, or null
if the tree does not contain the passed Any
. We've handled this
case already for you in the starter code.
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,
Any 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 valuetrue
.Good luck and have fun!
Create a method toMap
that accepts a BinaryTree<*>
and returns a Map<Any, Int>
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.
You will need to import cs125.trees.BinaryTree
.
We've provided some code to get you started.
For reference, cs125.trees.BinaryTree
is defined like this:
Note that you may need to cast tree.value
to Any
so that you can add it to your map.
Need more practice? Head over to the practice page.