# Practice with Recursion

Kotlin

Created By: Geoffrey Challen

/ Updated: `2022-07-20`

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

## Warm Up Debugging Challenge

But, would we want to miss out on another debugging challenge? No way!

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

Interactive Walkthrough

Click on an icon below to start!

## 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 this lesson's homework problemâ€”which is a tricky one!

Interactive Walkthrough

Click on an icon below to start!

## 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 `Comparable`

s, not `Object`

s.)

Interactive Walkthrough

Click on an icon below to start!

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

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

## More Practice

Need more practice? Head over to the practice page.