University of Toronto
CSC148F--Introduction to Computer Science, Fall 1996

Assignment 3a: Recursion Warm-up

Due electronically:  Thursday 21 November, 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 November 21st, 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 an OOT function that takes an integer and a pointer to the root of a binary tree of integers, and returns the number of occurrences of the integer within 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.  

Below is the function header, and the declaration of the node type that it uses:

       type treeNode :
           record
               num : int
               left, right : ^treeNode
           end record
       
       function frequency (value : int, root : ^treeNode) : int

 

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 frequency 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'' icon. 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:

• Hand trace a call to the recursive factorial function on slide 309. (Turning tracing on in OOT is not the same thing!) 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 frequency 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 frequency function. Use the questions on slides 328-331 to help you tackle it.

 

...footnote

This can be done only from our PC lab. Be warned that the lab may be very busy near the due date.