CSE 212 | Assignment

W06 Code: Trees

This assignment must be completed individually to ensure you are meeting all course outcomes. You should not complete this assignment within a group. If you obtain help from a tutor, the tutor should help you understand principles but should not help you answer these problems. It is an honor code violation to obtain answers for these problems from others including using the internet (i.e. sites that allow students to share their solutions).

Running and Debugging

You should not edit any files that have the comment DO NOT MODIFY THIS FILE at the top of them. Any edits you make to these files will be removed before grading.
Running all tests for this assignment: Click on Run and Debug in the sidebar, then select this week's code assignment from the drop-down at the top. Click the green Start Debugging button next to the drop-down. The integrated terminal will show the files being compiled and then the tests being run. It will print a summary of which tests passed and failed.
Running individual tests: Navigate to the test file ending in _Tests.cs in the week's code directory. Visual Studio Code will show inline buttons to Run Test for each test method, or to Run All Tests for each test class.
Debugging individual tests: Navigate to the test file ending in _Tests.cs in the week's code directory. Visual Studio Code will show inline buttons to Debug Test for each test method, or to Debug All Tests for each test class.
- If you put a breakpoint inside your code or inside the test, the only way to hit it will be by clicking Debug Test or Debug All Tests in this file.
- If you want to debug by printing output to the terminal, you must use Debug.WriteLine() to do so. Using that may require you to add using System.Diagnostics; to the top of the file. Using Console.WriteLine(), as is done in other parts of the template project, will not correctly print output to the console when a test is running. Any output generated with Debug.WriteLine() will appear in the Debug Console portion of the integrated terminal when clicking Debug Test or Debug All Tests in this file.

Instructions

As you solve the problems, remember to use the principles learned previously in the course:

Problem Solving Strategy: understand the problem, plan and design the solution, implement the solution, and evaluate the solution.
Evaluate Performance of Alternative Solutions: use big O to determine the best solution.
Understanding Code Using Reviews: analyze any code you have been given.
Finding Defects Using Tests: write tests to determine if your solution is working.
Articulating Answers for Technical Questions: imagine that you were asked one of these questions during an interview. Remember to ensure that you fully understand the problem and work through different scenarios manually. Consider how the data structure you are using will help you solve the problem. A notebook or a whiteboard can be very useful in this process.

All of the files for this assignment will be found in the course Git repository in the week06/code folder. You will commit changes to your own repository for your submission for this assignment.

Problem 1: Insert Unique Values Only

Update the Insert function of the Node class to only allow unique values to be added to the tree (thus creating a sorted set). The Insert function is already written to correctly insert values into the tree. However, the current implementation will cause duplicate values to be added to the tree.

Problem 2: Contains

Implement the Contains function in the Node class. This function is called by the Contains function in the BinarySearchTree to search for a value in the tree. If the value is found, true should be returned; otherwise return false. Hint: study the Insert function. You will need to use recursion to solve this problem.

Problem 3: Traverse Backwards

Implement the TraverseBackward function in the BinarySearchTree class. This function is called by the Reversed function to loop through the tree backwards (largest value down to the smallest value). The Reversed function allows you to write code using the foreach syntax like the following:


foreach(var value in myTree.Reversed())
{
	Console.WriteLine(value);
}

Hint: study the TraverseForward function to see how traversing forward is done.

Problem 4: Tree Height

Implement the GetHeight function in the Node class to get the height of the BinarySearchTree. The height of any tree (or subtree) is defined as one plus the height of either the left subtree or the right subtree (whichever one is bigger). If the tree has only the root node, then this would be 1 plus the maximum height of either subtree which would be 0. Therefore, the height of a tree with only the root node is 1. You will need to use recursion to solve this problem.

Problem 5: Create Tree from Sorted List

Implement the InsertMiddle function (note this function is defined outside the BinarySearchTree class) so that the CreateTreeFromSortedList function can successfully create a balanced tree from a sorted list of values. If we looped through the list of sorted values and added them (using the Insert function in the BinarySearchTree class) one at a time in order, then the resulting tree would look like a linked list. This is not desirable because it results in O(n) instead of O(log n).

To achieve a balanced tree, the InsertMiddle function should find the middle of the list (or sub-list … notice that the function takes a first and last value to keep track of what part of the list you are working with) and add it to the tree. After adding the middle value, then the middle value from the first half and the middle value from the second half should be added. This process (which is recursive) will result in a balanced tree.

The purpose for having the first and last parameters is so that we do not need to create new sublists when we make recursive calls. Avoid using list slicing to create sublists to solve this problem.

Please note that you do NOT need to use a balanced algorithms like AVL or red/black trees in this problem.

Grading

To receive full credit on this assignment, you must successfully complete any four of the five problems. If you complete all five problems you are eligible to receive extra credit.

Submission

When you have finished the assignment:

Make sure that all of your changes are committed to your course repository.
Push your latest changes to GitHub.
Return to I-Learn to submit a link to your GitHub repository.