University of Toronto
CSC148F--Introduction to Computer Science, Spring 1997
Assignment 3a: Recursion Warm-up

Due electronically:  Thursday 27 March, 6:00 pm
This assignment is worth 1 mark towards your grade in this course. Part marks will count.

The purpose of this assignment is to help everyone get comfortable with recursion before embarking on assignment 3. Although it is not due until March 27th, we urge you to try to complete it a week earlier. This little warmup is a very small assignment, and you will need the extra time to work on assignment 3. Also, doing this warmup assignment will help you to prepare for your upcoming midterm.

The problem

Write a function that takes an integer `num' and a pointer to the root of a binary tree of integers, and returns the smallest value greater than `num' in the tree, or `num'-1 if there is no value greater than `num' in the tree. The tree may or may not be a binary search tree, so you should not make any assumptions about the ordering of elements within the tree.  

How to hand in your assignment

We have written a driver program to test your function. It is available at the course web site. You must use this exact code as your starting point; just fill in the body of your smallestBigger function. Name the file containing your completed program 3a.t. When you have finished debugging and testing your function, and are convinced of its correctness, hand it in electronically using the ``Hand in (submit)'' command, found under the ``File Utilities''. (This can be done only from our PC lab. Be warned that the lab may be very busy near the due date.) You may hand in a solution more than once. In that case, we will have only a copy of your most recently submitted version.  

As with assignment 0, your solution will be marked by a program and the marking scheme will be tough. So you should therefore test your code thoroughly before handing it in. In addition, the same rules apply as with assignment 0. If you do not use the correct file name, or if you change our program in any way other than to insert the body of your function, your mark will be zero.  

Preparation for this assignment

Here are some suggested exercises to prepare you for this assignment:

• By hand, on a piece of paper, trace a call to the recursive factorial function on slide 309. The only trick to this is being meticulous enough not to lose track of where you are in the recursion.
• Clear up any questions that arise from this, and anything that is not clear from the recursion lectures.
• Get a copy of the starter code for this assignment and fill in the smallestBigger function so that it always returns 0. (You can fill it in properly later.) This will allow you to run the program and see how it builds and draws a tree. Try that out. Notice how the tree is drawn sideways. Why did we choose to draw it that way?
• Now hand trace something a bit harder: the printTree procedure from the starter code for this assignment. Trace it on a tree with at least 7 nodes. What is the indent parameter for?
• Optional (although you should eventually be able to do this): for a bigger challenge, hand trace a call to the buildTree function. Use an example where numValues is at least 7. What can you say about the shape of tree that it builds? What about the placement of values in the tree?
• Now you should be well ready to write your smallestBigger function. Use the questions on slides 328-331 to help you tackle it.