## CS 112 Lab 9: Binary Search Trees

### Objectives:

In this exercise, you will:
1. Complete a linked-node-based binary search tree class.
2. Practice building recursive operations.
3. Practice thinking recursively.

### Introduction

Today's exercise is to complete a class named BST from which binary search tree objects can be created. (See your textbook for definitions of tree, binary tree, and binary search tree.) The exercise provides you with a test-class and a partially-built BST class; your task is to complete the BST class.

### Getting Started

Begin by creating a new project for this week's files. Download tester.cpp, BST_Tester.h, BST_Tester.cpp, BST.h, BST.cpp, and Exception.h. Import these files into your project, open the files, and personalize their opening documentation. Then take a few minutes to look them over, to become familiar with their contents. Save/compile, and run the tests, to verify that everything works correctly at the outset.

### The BST Constructor

As you can see, our BST class contains just two instance variables:

```   Node*    myRoot;       // pointer to the first item we insert
unsigned myNumItems;   // number of items I contain
```
If our BST is empty, then myRoot should have the value NULL and myNumItems should equal zero.

In BST_Tester.cpp, uncomment the call and definition of testConstructor. Save/compile, and verify that you get compilation errors. Take a few moments to study testConstructor(), to see what you must do to pass it. Modify BST.h and BST.cpp as necessary to fix these errors; then save/recompile.

When your project compiles correctly, run the tests. When your project passes all tests, continue.

### The insert() Method

Your BST class now provides methods to:

• Define an empty BST;
• Determine whether a BST is empty or not;
• Determine the number of items in a BST; and
• Reclaim the dynamic memory of a BST.

Our next task is to be able to insert items into a BST. The insert(it) method adds an item it to the tree by storing it in a node such that:

• all nodes to the "left" of the node containing it contain items that are less than it; and
• all nodes to the "right" of the node containing it contain items that are greater than it.
Note that if we use a simple approach to insert() in which the first item is stored in the root node, the second item is stored in a child node of the root node, and so on, then the order in which we add items can make a big difference in the shape of the tree. For example, if we insert items in a "carefully chosen random" order: 44, 66, 22, 55, 11, 77, 33, then our tree will be balanced:

A tree's shape can be characterized in different ways. One way is by comparing its height, diameter, and maximum width:

• A tree's height is the number of nodes on the longest path from the root node to any of the leaf nodes.
• A tree's diameter is the number of nodes on the longest path between any two leaves in the tree. This path often includes the root node, but not necessarilly.
• A tree's maximum width is the largest number of nodes on any given level of the tree.
The preceding tree's height is 3, its diameter is 5, and its maximum width is 4. If a binary search tree is balanced, then its height should be about log2(n), where n is the number of items in the tree.

By contrast, if we insert items in ascending order: 11, 22, 33, 44, 55, 66, 77, then our tree will be imbalanced one way:

This tree's height is 7, its diameter is 7, and its maximum width is 1.

Likewise, if we insert the items in descending order : 77, 66, 55, 44, 33, 22, 11, then our tree will be imbalanced the other way:

As before, this tree's height is 7, its diameter is 7, and its maximum width is 1.

In BST_Tester.cpp, uncomment the call to and definition of testInsert(). Save/compile, and verify that you get a compilation error indicating that insert() is undeclared.

Add a prototype of insert() to our BST class; then recompile and verify that only a linking error remains.

In BST.cpp, create a stub for BST::insert(). Recompile, and when all errors have been eliminated, run the test. Then define BST::insert() so that it passes the test. Here is a hint, in case you get stuck, but do your best to build this method without looking at it. Run the project, and verify that everything works correctly at the outset.

### The contains() Method

Uncomment the definition and call of BST_Tester::testContains(). Take a few minutes to look over the tests it contains, specifically how contains() is used. As can be seen, the contains(it) method returns true if it is in its BST; otherwise it returns false. Save/compile your project. You should see an error indicating that there is no method matching the calls in our test-method.

Modify BST.h and BST.cpp as necessary to fix any complilation/linking errors, using an approach similar to the approach used in insert(). Recompile and run the tests. If you get stuck, here is a hint, but don't use it unless you have to.

Continue when your method passes the test.

### Three Traversal Methods

To traverse a data structure is to pass through each of its items, processing each item in turn. For example, outputing the values in an array, vector, or list usually involves traversing the structure and outputing each item in turn.

When it comes to binary search trees, there are a variety of ways to traverse a BST:

• A preorder traversal "processes" the item in a node before the items in the left and right subtrees are (recursively) processed.
• A postorder traversal "processes" the item in a node after the items in the left and right subtrees are (recursively) processed.
• An inorder traversal "processes" the item in a node after the items in the left subtree have been processed, but before the items in the right subtree have been (recursively) processed.
To illustrate, the BST class contains a traversePreorder() method, defined as follows:
```   void BST::traversePreorder() {
if ( !isEmpty() ) {
myRoot->traversePreorder();
}
}```
If the BST is not empty, this method "passes the buck" by sending the traversePreorder() message to the node whose address is in myRoot. The Node struct defines that (recursive) method as follows:
```   void BST::Node::traversePreorder() {
// 1. process myItem first (preorder)
processItem();
// 2. then recursively process the items in the left subtree
if (myLeft != NULL) {
myLeft->traversePreorder();
}
// 3. then recursively process the items in the right subtree
if (myRight != NULL) {
myRight->traversePreorder();
}
}```
The processItem() method can be defined to do any kind of processing of a node's item. To illustrate, our Node struct defines processItem() to insert a space and then myItem into cout:
```   void BST::Node::processItem() {
cout << ' ' << myItem;
}```
Uncomment the call and definition of BST_Tester::testTraverse() and take a moment to look over its tests. Your final task is to define traversePostOrder() and traverseInorder() methods that will produce the output expected by the test-method. Use the provided traversePreorder() method as a model; the other two traversal methods are quite similar.

When your code passes all the tests, congratulations! You now have a functional binary search tree class!