# CS210 Lab: Binary Search Tree

## Lab Exercise:

Click the little computer above for a detailed description.
For this exercise you will be asked to implement `getCount` and `getHeight` functions.

## 1. Definition of a Binary Search Tree

A binary tree is a structure with two properties: a shape property and a property that relates the keys of the elements in the structure. The shape property, binary tree is a structure in which each node is capable of having two successor nodes, called children. Each of the children, being nodes in the binary tree, can also have two child nodes, and so on, giving the tree its branching structure. The beginning of the tree node is called the root. The level of nodes refers to its distance from the root.

A binary search tree is a binary tree in which the key value in any node is greater than the key value in its left child and any of its children (the nodes in the left subtree) and less than the key value in its right child and any of its children (the nodes in the right subtree).

### 1.2 Applications of a Binary Search Tree

• Search applications, Syntax tree for parse expression, 3D video games, compression algorithm and etc.
• Dictionary Search, Sorting and Searching informations from databases.

### 1.3 Typical Operations of a Binary Search Tree

 void insert ( newDataItem ) Insert data item bool retrieve ( searchKey, searchDataItem ) Retrieve data item bool remove ( deleteKey ) Remove data item void writeKeys () Output keys void showStructure () Output the tree structure int getHeight () Height of tree int getCount () Number of nodes in tree

## 2. Detail on Binary Search Tree ADT

### Data Items

The data items in a binary search tree are of generic type DataType. Each data item has a key (of generic type KeyType) that uniquely identifies the data item. Data items usually include additional data. The data items must provide a function called getKey that returns a data item's key.

### Operations

`BSTree()`

Requirements: None

Results: Default constructor. Creates an empty binary search Tree.

`BSTree ( const BSTree<DataType,KeyType>& other)`

Requirements: None

Results:

Copy constructor. Initializes the binary search tree to be equivalent to the other BSTree object parameter.

`BSTree& operator=( const BSTree<DataType,KeyType>& other)`

Requirements: None

Results:

overloaded assignment operator. Sets the binary search tree to be equivalent to the other BSTree object parameter and returns a reference to this object.

`~BSTree ()`

Requirements: None

Results:

Destructor. Deallocates the memory used to store the binary search tree.

`void insert( const DataType& newDataItem)`

Requirements: None

Results:

Inserts `newDataItem` into the binary search tree. If a data item with the same key as `newDataItem` already exists in the tree, then update that data item with `newDataItem`.

`bool retrieve( const KeyType& searchKey, DataType& newDataItem)const`

Requirements: None

Results:

Searches the binary search tree for the data item with key `searchKey`. If this data item is found, then copies the data item to `searchDataItem` and returns `true`. Otherwise, returns `false` with `searchDataItem `undefined.

`bool remove( const KeyType& deleteKey)`

Requirements: None

Results:

Delete the data item with key `deleteKey` from the binary search tree. If this data item is found, then deletes it from the tree and returns `true`. Otherwise, returns `false`.

`void writeKeys() const`

Requirements: None

Results:

Outputs the keys of the data items in the binary search tree. The keys are output in ascending order on one line, separated by spaces.

`void showStructure() const`

Requirements: None

Results:

Outputs the keys in the binary search tree. The tree is output with its branches oriented form left (root) to right (leaves)- that is, the tree is output rotated counter-clockwise ninety degrees from its conventional orientation. If the tree is empty, outputs "Empty tree". Note that this operation is intended for debugging purposes only. It only supports data items with key values that are one of C++'s predefined data types (int, char, and so forth) or other data structures that have overridden ostream `operator<<`.

#### Helper Functions

We have seen similiar pairs of functions already in the previous resursion lab. With functions that are naturally implemented using recursion, it is useful to have a separate function that provides a public interface to the class. That function then calls a private "helper" function with a set of appropriate paramenters. The helper function performs the recursive work, while the public interface function ensures that the recursive process gets started correctly and any return value is sent back to the caller.

#### Reference pointers

To define a parameter that is a reference to a pointer, you simply use both & and * in the data type specification for the parameter. For example, the following code declares the helper function (`buildHelper`) for the `build` function. The function takes a reference to a pointer to an expression tree node so that if a new node should be added to the tree, it can be allocated and added by simply assigning the newly allocated node to the `node` parameter.

```template<typename DataType>
void ExprTree<DataType>::buildHelper(ExprTreeNode*& node)
{
......

}```

Note: the order of the * and & operators is significant. "*&" means a reference to a pointer, but "&*" means a pointer to a reference, which is nonsense to the compiler.

## 3. Lab Exercise

### You need to implement `getCount()` and `getHeight()` operations for this lab exercise.

#### Step 1: Calculate the number of nodes a binary search tree contains.

It can be useful to know how many nodes a binary search tree contains. The following Binary Search Tree ADT operation adds the capability to interrogate a tree to find out how many data items it contains.

```int getCount () const ```

Requirement: None

Results:

Returns the count of the number of data items in the binary search tree. That is the total number of nodes from left tree, right tree and the parent.

#### Step 2: Calculate the height of the binary search tree.

Binary search trees containing the same data items can vary widely in shape depending on the order in which the data items were inserted into trees. One measurement of a tree's shape is its height. This statistic is significant because the amount of time that it can take to search for an item in a binary search tree is a function of the height of the tree.

The height of any node in a tree is the number of edges (links or steps) on the longest path from that node to any leaf node under it. A leaf node has a height of 0, as does a tree with only one node (the root). An empty tree has no defined height—for our purposes we will use the sentinel value -1.

You can compute the height of a binary search tree using a post-order traversal and the following recursive definition of height for a tree rooted at a given node p.

`int getHeight() const`

Requirements: None

Results:

Returns the height of the binary search tree.

#### Detailed implementation:

Step 1:

• Get the files:
```Click here To get the zipped files for this exercise.

Extract all of the files.  Open the Binary_Tree folder and double
click on binarytree.sln.
This will open up the project.
```
• There are three files used in this program:
• BSTree.h — templated binary search tree implementation. getCount()and getHeight()functions are in this file.
• config.h — controls to enable or disable getCount() and getHeight() functionality.
• test.cpp — the main program.

Step2:

• Implement getCount and getHeight. You will find prototypes and partial function definitions for both in BSTree.h
• Your output should look similar to the following.

### Reference:

(Brandle, Geisler, Roberge and Whittington) C++ Data Structures, A Laboratory Course (Third Edition).