**COM 1201 Algorithms and Data Structures 2**

**Homework #2 -- Due Monday, February 28th**

## **BINARY SEARCH TREES**

#### Winter 2000 -- Professor Futrelle

College of Computer Science, Northeastern U., Boston, MA

Details posted 2/22/00.

This homework assignment is a written one, not a machine problem.
It deals with binary search trees (BST) and is based on portions of Chapter 12 of the text.
For the readings that are appropriate for this assignment, see the syllabus entry
for February 24th. (Syllabus link)

For the general requirements for homework in this class, see the
Homework #1 page.

**1.**
Insert the following sequence of elements into an initially empty BST
and draw the resulting BST: 3, 5, 1000, 450, 12, 30, 2, 200, 17.

**2.**
Insert the same elements as before into an empty BST but in the following order,
and draw the resulting BST: 2, 3, 5, 12, 17, 30, 200, 450, 1000.

**3.**
Discuss the differences between 1 and 2 and how the different tree morphology might
affect search and insert efficiency.

**4.**
Suppose that we have an estimate ahead of time of how often search keys are accessed
in a binary tree. Should the keys be inserted into the tree in increasing or decreasing
order of likely frequency of access? Explain your answer. (This is Exercise 12.52 of
the textbook.)

**5.**
Students sometimes confuse the organization, purpose and manipulations of the binary
tree making up the heap and binary search trees. Write a brief paragraph that
points out the similarities of the two and more importantly, the very great differences
between the two types of trees. For example, what would be a quick way to look at
a tree and immediately know that it is one or the other?

**6.**
Build a BST by insertion of items in the following order: 3, 9, 4, 8, 7, 1, 5, 2, 6
Compute the average number of steps (number of links followed) to search for and find
an item that is present in the tree.
That is, do one search for each of the distinct keys and average the result.