#### Return to Index

#### MP3: Restaurant View Revisited : `12/01/2021`

#### MP3: Restaurant Graphs and Hashing : `11/30/2021`

#### MP3: Practical Sorting : `11/29/2021`

#### Implementing a Map : `11/19/2021`

#### Hashing : `11/18/2021`

#### Binary Search : `11/17/2021`

#### MP2: Related Restaurants : `11/16/2021`

#### MP2: Restaurant Activity : `11/15/2021`

#### Quicksort : `11/12/2021`

#### Merge Sort : `11/11/2021`

#### Sorting Algorithms : `11/10/2021`

#### MP2: Client-Server Communication : `11/09/2021`

#### MP2: CSV to JSON : `11/08/2021`

#### Graph Algorithms : `11/05/2021`

#### Graphs : `11/04/2021`

#### Practice with Recursion : `11/03/2021`

#### MP1: Search and Callbacks : `11/02/2021`

#### MP1: Views and UI : `11/01/2021`

#### Trees and Recursion : `10/29/2021`

#### Trees : `10/28/2021`

#### Recursion : `10/27/2021`

#### MP1: Serialization and Searching : `10/26/2021`

#### MP1: Serialization and Sorting : `10/25/2021`

#### Lists Review and Performance : `10/22/2021`

#### Linked Lists : `10/21/2021`

#### Algorithms and Lists : `10/20/2021`

#### Continuing MP0 : `10/19/2021`

#### Getting Started with MP0 : `10/18/2021`

#### Lambda Expressions : `10/15/2021`

#### Anonymous Classes : `10/14/2021`

#### Practice with Interfaces : `10/13/2021`

#### Implementing Interfaces : `10/12/2021`

#### Using Interfaces : `10/11/2021`

#### Working with Exceptions : `10/08/2021`

#### Throwing Exceptions : `10/07/2021`

#### Catching Exceptions : `10/06/2021`

#### References and Polymorphism : `10/05/2021`

#### References : `10/04/2021`

#### Data Modeling 2 : `10/01/2021`

#### Equality and Object Copying : `09/30/2021`

#### Polymorphism : `09/29/2021`

#### Inheritance : `09/28/2021`

#### Data Modeling 1 : `09/27/2021`

#### Static : `09/24/2021`

#### Encapsulation : `09/23/2021`

#### Constructors : `09/22/2021`

#### Objects, Continued : `09/21/2021`

#### Introduction to Objects : `09/20/2021`

#### Compilation and Type Inference : `09/17/2021`

#### Maps and Sets : `09/16/2021`

#### Lists and Type Parameters : `09/15/2021`

#### Imports and Libraries : `09/14/2021`

#### Multidimensional Arrays : `09/13/2021`

#### null : `09/10/2021`

#### Algorithms and Strings : `09/09/2021`

#### Strings : `09/08/2021`

#### More About Functions : `09/07/2021`

#### Errors and Debugging : `09/03/2021`

#### Functions : `09/02/2021`

#### Algorithms I : `09/01/2021`

#### Loops : `08/31/2021`

#### Arrays : `08/30/2021`

#### Compound Conditionals : `08/27/2021`

#### Conditional Expressions and Statements : `08/26/2021`

#### Operations on Variables : `08/25/2021`

#### Variables and Types : `08/24/2021`

#### Welcome to CS 124 : `08/23/2021`

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

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 today'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!

### Solution Walkthrough

Interactive Walkthrough

Click on an icon below to start!

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

### Solution Walkthrough

Interactive Walkthrough

Click on an icon below to start!