Data structure and alogorithm

Assignment 11: Binary Search Trees

COSC 2336: Data Structures and Algorithms

Fall 2020

Objectives • Practice recursive algorithms • Learn how to construct a binary tree using pointers/linked nodes • Learn about binary tree traversal

Description In this assignment you will be given the beginning of a BinaryTree implementation using linked nodes via pointers. You will be implementing some of the basic function of a BinaryTree abstract data type. The abstraction we are using for the BinaryTreeNode and the BinaryTree are similar to the Shaffer BSTNode (pg. 156,161) and the BST abstract class and linked pointer implementation (Shaffer pg. 171), but we will define our own version and simplify some of the functions and interface.

You have been given a BinaryTree.[cpp|hpp] file that defines the BinaryTreeNode structure and BinaryTree class. This class is current not templatized, the constructed trees only hold items of simple type int (one of the extra credit opportunities suggests you templatize your resulting class). The BinaryTree has a constructor, and you have been provided a tostring() method and an overloaded operator<<() so that you can display the current contents of the tree.

Setup For this assignment you will be given the following files:

File Name Description assg11-tests.cpp Unit tests for the member functions and queue

functions you are to write. BinaryTree.hpp Header file for the BinaryTree class that

that you are to add function prototypes for the new member functions into.

BinaryTree.cpp Implementation file, the implementation of the BinaryTree class member methods for this assignment go here in this file.

Set up a multi-file project to compile the .cpp source files and run them as shown for the class. The Makefile you were given should be usable to create a build project using the Atom editor as required in this class.

The general approach you should take for this assignment, and all assignment is:

1. Set up your project with the given starting code. The files should compile and run, but either no tests will be run, or tests will run but be failing.

2. For this project, start by uncommenting the first TEST_CASE in the assg11-tests.cpp file. These are the unit tests to test the functionality of your BinaryTree insert() function, the class recursive method you are to implement.

1

3. Add the insert() public and private prototypes to the BinaryTree.hpp header file. 4. Add a stub for your two insert() member function to the BinaryTree.cpp implementation file. The public

insert() is a void function so it can initially be empty. The private version of the function should return a pointer to a BinaryTreeNode, so you should create a new node and return it initially from this function.

5. Your code should compile and run now. Make sure after adding the public and private stub methods your code compiles and runs. However, your unit tests will be failing initially.

6. Incrementally implement the functionality of your insert() member functions. Most of the work is actually done by the private insert() function. You should try to add no more than 2 or 3 lines of code, and then make sure your program still compiles and runs. Start by adding code to get the first failing test to pass. Then once that test passes, move on to the next failing tests until you have all tests passing. If you write something that causes a previously passing test to fail, you should stop and figure out why, and either fix it so that the original test still passes, or remove what you did and try a new approach.

7. Once you have the insert() member function implemented and all unit tests passing, you should then move on to the other functions in the order suggested. Some functions use previous ones in this assignment, so do them in the order given for you in the tasks below.

Tasks You should set up your project/code as described in the previous section. In this section we give some more details on implementing the member functions for this assignment. You should perform the following tasks for this assignment:

1. In order to test your class, we first have to get a working capability to insert new items into the BinaryTree, which isn’t the simplest task to start with, but we can’t really test others until we can add new items. For many of the functions in this assignment, you will be required to implement them using a recursive function. Thus many of the functions for your BinaryTree will have a public function that asks as the interface that is called by users of the BinaryTree, and a private version that actually does the work using a recursive algorithm. I will give you the signature you need for the insert() functions: class BinaryTree { private:

BinaryTreeNode* insert(BinaryTreeNode* node, const int item);

public: void insert(const int item);

}

Lets start first with the public insert() function. This function is the public interface to insert a new item into the tree. Since we are only implementing a tree of int items, you simply pass in the int value that is to be inserted. This function basically only needs to call the private insert() function, passing in the current root of the tree as the first parameter, and the item to be inserted as the second parameter. Notice that the private insert() returns a pointer to a BinaryTreeNode.

The private insert() function is a recursive function. The base case is simple. If the node you pass in is NULL, then that means you have found the location where a new node should be created and inserted. So for the base case, when node is NULL you should dynamically create a new BinaryTreeNode item, assign the item and make sure that the left and right pointers are initialized to NULL. When you create a new node like this, you should return the newly created BinaryTreeNode as a result from the insert() function (notice that the private insert() should always return a BinaryTreeNode*). This is because, when a new node is allocated, it gets returned and it needs to be assigned to something so it gets inserted into the tree. For example, think of what happens initially when the BinaryTree is empty. In that case the root of the tree will be NULL. When you call the recursive insert() on the initially empty tree, you need to assign the returned value back into root in the non-recursive function (and you also need to increment the nodeCount by 1 in your public non-recursive function).

The general cases for the recursion are as follows. Since we are implementing a binary search tree, we need to keep the tree organized/sorted. Thus in the general case, remember that we have already tested that the node is not NULL, thus there is an item in the node->item. So for the general case, if the item we are inserting is less than or equal to node->item, then we need to insert it into the left child subtree (it is important to use <=

2

comparison to determine if to go left here). To do this you will basically just call insert() recursively with the item to be inserted, and passing in node->left as the first parameter. Of course, in the case that the item is greater than the one in the current node, you instead need to call insert() on the node->right child subtree.

And finally, make sure you take care of correctly returning a result from the recursive insert(). Here when you call insert() on either the left or right child subtree, the function should return a BinaryTreeNode*. For example, imagine that you are inserting into the left child, and there is no left subtree, and thus left will be NULL. In that case the recursive call to insert() will create a new node dynamically and return it. So the return value from calling insert() needs to be assigned back into something. If you are calling insert() on the left child, the returned result should be assigned back into node->left, and if you are calling on the right child, the returned result should be assigned back into node->right. Again this is because when we finally find where the node needs to be linked into the tree, we will do it at either an empty left or right subtree child. Thus in order to link the newly created node into the tree, we need to assign the returned pointer back into either node->left or node->right appropriately. And finally, after you call insert() recursively in the general case, you do have to remember that you always have to return a BinaryTreeNode*. For the base case, when you dynamically create a new node, the new node is what you return. But in the general case, you should simply return the current node. This will get (re)assigned when you return back to the parent, but this is fine and expected.

To summarize, you need to do the following to implement the insert() functionality:

• The public insert() should simply call the private insert() on the root node. • In the public insert() the return result should be assigned back into root. • The public insert() is also responsible for incrementing the nodeCount member variable. • For the private recursive insert() the base case occurs when a NULL node is received, in which case a new

BinaryTreeNode is dynamically created and returned. • For the general case, if node is not NULL, then you instead either need to call insert() recursively on the

left or right subchild, depending on if the item to be inserted is <= or > the node->item respectively. • Don’t forget in the general case, that the returned result from calling insert() needs to be assigned back

into left or right as appropriate. • And finally, the recursive insert() always returns a value, and in the general case you should simply just

return the node as the result.

2. Next we have a relatively easier set of tasks to accomplish. Once you have insert() working and tested, we will implement a function to determine the current height() of the tree. You should read our textbook to make sure you know the definition of the height of a tree.

height() needs 2 functions again, a public function which is the interface, and a private function that is recursive and does the actual work. Both the public and private height() functions should be declared as const functions, as they do not actually modify the contents of the tree. Both functions return an int result. The public function doesn’t have any input parameters, but the private function should take a single BinaryTreeNode* as its input parameter.

The public height() function should be very simply, it should simply call the private height() on the root node of the binary tree, and return the resulting calculated height.

For the private height() function, the base case is that if node is NULL then the height is 0, so you should return 0 in that case. Otherwise, in the general case, the height is conceptual 1 plus the height of the bigger of the heights of the two subtree children left and right. Thus to calculate the height for a given node, recursive calculate height on both the left and right children, find the maximum of these two, add 1 to it, and that is the height of the node.

3. The third and final task is to implement the clear() abstract function. The clear() function basically clears out all of the stored items from the tree, deallocating and returning the memory used for the node storage back to the OS.

As with all of the functions for this assignment, clear() needs both a public function that acts as the interface, and a private recursive version that does all of the work. The implementation of the public clear() is almost as simple as the previous height() function. The public clear() should simply call the private clear(), passing in the current root of the tree. Both the public and private versions of clear() should be void functions, they do not return any result or value.

3

The private recursive clear() is a void function, as we mentioned, and it takes a single BinaryTreeNode# parameter as its input. This function is also relatively rather easy. The base case is that, if node is NULL then you don’t have to do anything, simply return, as you have reached the end of the recursion in that case. For the general case, all you need to do is simply call clear() recursively on the left and right subtree children first. Then after this you can safely call delete on the node, because all of the nodes in the two subtree children will have been deleted by the recursion, and now you can safely delete and free up the memory for the node.

Example Output Here is the correct output you should get from your program if you correctly implement all the class functions and successfully pass all of the unit tests given for this assignment. If you invoke your function with no command line arguments, only failing tests are usually shown by default. In the second example, we use the -s command line option to have the unit test framework show both successful and failing tests, and thus we get reports of all of the successfully passing tests as well on the output.

$ ./test =============================================================================== All tests passed (40 assertions in 4 test cases)

$ ./test -s

------------------------------------------------------------------------------- test is a Catch v2.7.2 host application. Run with -? for options

------------------------------------------------------------------------------- <basic BinaryTree> test basic BinaryTree functionality ------------------------------------------------------------------------------- assg11-tests.cpp:30 ...............................................................................

assg11-tests.cpp:35: PASSED: CHECK( t.size() == 0 )

with expansion: 0 == 0

... output snipped ...

=============================================================================== All tests passed (40 assertions in 4 test cases)

Assignment Submission A MyLeoOnline submission folder has been created for this assignment. For these assignments I do not need the test files, nor do I need your visual studio project files or a whole zip/archive of your project directory. For this assignment you have 2 files to submit: BinaryTree.hpp, BinaryTree.cpp. These should be the only files you added code into (besides uncommenting tests in the test file). Also make sure that the names are the same as originally given to you (do not rename them Assignment or Program01, etc., do not change assg to Assg, make sure the case of the file names is CamelCaseNotation). A large portion of your programs will be tested automatically, so keeping the files names the same and making sure your code passes the unit tests as given to you is important for being able to grade your submission. A MyLeoOnline submission folder has been created for this assignment. There is a target named submit that will create a tared and gziped file named assg02.tar.gz. You should do a make submit when

4

finished and upload your resulting gzip file to the MyLeoOnline Submission folder for this assignment.

$ make submit tar cvfz assg11.tar.gz assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp assg11-tests.cpp assg11-main.cpp BinaryTree.hpp BinaryTree.cpp

Requirements and Grading Rubrics Program Execution, Output and Functional Requirements

1. Your program must compile, run and produce some sort of output to be graded. 0 if not satisfied. 2. (40 pts.) insert() functionality is implemented correctly. Base and general cases are written as described.

Functions work for trees with items and when tree is empty.

3. (30 pts.) height() functionality is implemented correctly. Correctly implement stated base and general cases using recursion.

4. (30 pts.) clear() functionality is implemented correctly. Correctly implement stated base and general cases using recursion.

5. (10 pts. extra credit) Of course it is not really useful to have a BinaryTree container that can only handle int types. Templatize your working class so it works as a container for any type of object. You should rewrite the unit tests to use your template class, and submit your rewritten tests. You will need to modify your header and Makefile build to build using a template rather than a separately compilable file. If you do this, submit your code first of the working non-templatized BinaryTree.[hpp|cpp] files.

6. (5 pts. extra credit) Implement a printTree() method. The tostring() method I gave you doesn’t really show the structure of the tree. Of course if you had a graphical environment you could draw a picture of the tree. But if you only have a terminal for output, you can display the tree as a tree on its side relatively easy. To do this, you need again both a public and private printTree() method. The private method is the recursive implementation, and as usual it takes a BinaryTreeNode* as a parameter, and a second parameter indicate the offset or height of this node in the tree. If you perform a reverse preorder traversal of the tree, spacing or tabbing over according to the tree height, then you can display the approximate structure of the tree on the terminal. Recall that preorder traversal is performed by visiting left, then ourself, then our right child. So a reverse preorder is performed by first visiting our right, then ourself, then our left child.

7. (10 pts. extra credit) The BinaryTree is missing a big piece of functionality, the ability to remove items that are in the tree. You can read our textbook for a description of how you can implement functions to remove items from the tree. It is a good exercise, and quite a bit more challenging than the insert(). The simplest case is if you want to remove a node that is a leaf node (both left and right are NULL, indicating no child subtrees). When removing a leaf, you can simply delete the node and set the parent pointer in the tree to this node to NULL. When the node only has 1 subtree, either the left or the right, you can also still do something relatively simple to assign the orphaned subtree back to the parent, then delete the node with the item that is to be removed. But when the node to be deleted also has both left and right child subtrees, then you need to do some rearrangements of the tree. The Shaffer textbook discusses how to implement removal from a binary tree as an example you can follow.

Program Style Your programs must conform to the style and formatting guidelines given for this class. The following is a list of the guidelines that are required for the assignment to be submitted this week.

1. Most importantly, make sure you figure out how to set your indentation settings correctly. All programs must use 2 spaces for all indentation levels, and all indentation levels must be correctly indented. Also all tabs must be removed from files, and only 2 spaces used for indentation.

2. A function header must be present for member functions you define. You must give a short description of the function, and document all of the input parameters to the function, as well as the return value and data type of

5

the function if it returns a value for the member functions, just like for regular functions. However, setter and getter methods do not require function headers.

3. You should have a document header for your class. The class header document should give a description of the class. Also you should document all private member variables that the class manages in the class document header.

4. Do not include any statements (such as system("pause") or inputting a key from the user to continue) that are meant to keep the terminal from going away. Do not include any code that is specific to a single operating system, such as the system("pause") which is Microsoft Windows specific.

6