CSE 331 – Project 2 Binary Search Tree
TA: Xiao Zhang
zhan1387@msu.edu
Due Date: 11:59 pm Feb 21, 2020
Help Room: Thursdays: 6:20pm-7:50pm, Fridays: 4:00pm-6:00pm both days are in room 3112EB
1 Project Description
In this project, you will implement a binary search tree. Your binary search tree will be used to store and manipulate data from given text file.
You have been given code to implement a program that will load and manipulate the data from the numbers.txt file. The main program stores the numbers in a vector, and then builds a binary search tree based on the vector.
Your job is to complete the implementation of the following methods in BinarySearchTree class:
1. Insert: Inserts an item into the tree. No need to balance the tree. This should be O(h) where h is height of the tree.
2. InorderTraverse: Traverses the tree in order. In addition, there is an- other parameter: vector. The vector is expected to have all elements in the tree by the same order as visited by each recursion. This should be O(n).
3. DeleteNode: Deletes an element of the tree. This should be O(h).
4. Filter: Deletes all nodes that do not have the desired property keeping only ones with the property. This should be O(n). Provide an memory efficient implementation, i.e., O(1) space.
5. ForEachInterval: perform some function to each node of the tree in range of interval [a,b] where a,b are parameters of the method. Provide a memory efficient implementation, i.e., O(1) space. The running time should be equal to h plus number of elements satisfying the interval.
6. VerifyBinarySearchTree: returns true if the tree has properties of binary search tree, e.g., value of left child node is less than that of its parent. Return false otherwise. This should be O(n). Provide a memory efficient implementation, i.e., O(1) space.
1
I recommend that you implement all of your functions in the private space, and then place calls to private methods in the public methods. This will reduce the amount of code you write when overloading the const methods.
You may not use anything from the STL for this project. You may use IO for debugging, but be sure to remove it from your completed project. You will be marked down for any debugging IO left in your project. As usual, you may not change the signatures of the public methods, or the way in which the tree class interacts with the rest of the program. You may add any private member variables or methods to BinarySearchTree class to help you complete the project.
2 Checklist
Make sure that your implementation has
• no memory leak. That is, every pointer that allocated the memory is eventually deallocated. Every new operation has the corresponding delete operation when its job is done.
• no segmentation fault. Be careful when managing pointers during inser- tion/deletion of nodes.
• running time requirement as above.
• comments according to project guideline.
Remark. Some functions will be graded manually for space/time requirement
after due date.
3 Sample Test Cases
The program will take one input which is a file containing integers line-by-line. Your program will then read the file and store the integers in a vector.
The program builds a binary search tree by inserting elements from the vector. Then, it traverses the tree in order and puts values according to the order visited into another vector. There will be manipulation of the tree using filter, forEachInterval, delete method. As usual, main.cpp does the job for you. You have to complete implementation of the BinarySearchTree class.
4 Project Deliverables
The following files must be submitted via Mimir no later than 11:59 pm Feb 21, 2020.
1. Tree.h – contains your implementation of binary search tree.
2