Kotlin
Java

Practice with Recursion
Java

Created By: Geoffrey Challen
/ Updated: 2021-11-01

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

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

Show how to compute the depth of a tree.

Tree 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 today's homework problem—which is a tricky one!

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

Repeat the findValue method in this somewhat different context. Next, modify the tree to be more efficient by modifying add and then exploiting that in findValue. (At that point the tree should store Comparables, not Objects.)

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough

Show how to complete the homework problem above. Feel free to cover multiple approaches!

Solution Walkthrough