CS 14 - Lab 8
CS 14
Homepage
This lab is intended to give you some hands-on experience working with
some of the Binary Search Tree (BST) operations that we haven't
necessarily covered in the home programming assignments this quarter.
Using Recursion
Since BST's are a recursively defined data structure (base case: the
tree is empty. Recursive case: a node with two trees as children), it
is easy and natural to implement most of the BST operations on them
recursively.
However, there is one problem with this: recursion is inefficient in
terms of computation time. When writing basic tools like BSTs or
Linked-Lists, especially if you hope to reuse the tools in the future,
it is mildly important to be aware of performance concerns like this.
The Assignment
7 points
Working with a partner (1 computer per pair), download bst.cc. This is an all-recursion implementation of
a BST. Convert the following functions to be iterative:
- find
- insert
- findMinVal
- findMaxVal
.6 points
Convert remove to be iterative.
Some functions on binary trees CANNOT be done iteratively, they
require either explicit recursion or the use of a stack/queue to store
parts of the tree that must be checked. Write the following functions
recursively
.2 points int size(TreeNode* root)
.2 points int maxDepth(TreeNode* root)
.2 points int divisByN(TreeNode* root, int n)
© 2003 UC Riverside Department of Computer Science &
Engineering. All rights reserved.