Guess what? Today we'll be doing more practice with binary trees! And recursion! What could be more fun?
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 today'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.