Practice with RecursionJava
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.)
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!
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.
More Practice
Need more practice? Head over to the practice page.