COP3530 Programming Assignment 1 – Binary Search Tree

Description

In this programming assignment, you are supposed to implement a Binary Search Tree (BST). Each node of the BST will be a string. The directions are on Stepik.

You are required to submit the code in C++ on the Stepik platform and also upload it on canvas as a .cpp file. Three test cases will be provided to you to test your output on Stepik but you will be graded on 16 test cases including the three that are available to you. Each test case you pass, earns you 5 points. Therefore, 80 points are for implementation.

You are also required to submit a commentary in a docx or txt file explaining:

1. The complexity of your code (each function)

2. Why did you choose the implementation you did?

3. What challenges you encountered for this project?

4. How do you see this project connecting to your prior course experience?

This carries 20 points (5 points each for the four topics). I expect that you will write anywhere between 1~2 pages.

Notes:

1. The fourth test case is fake and is deliberately programmed to avoid access to other students’ code. So if you pass first three and get a score of 0.75, that is equal to 100%

2. Another pro-tip: Instead of using the submit button, use the Run button next to submit to test your own test cases. This is strongly encouraged and it is a good practice to create your own test cases. Anyone who creates them and needs help on verification, feel free to contact me or use slack to verify test cases with your peers.

3. The assignment is new and you will be the first batch to work on it. So if you find bugs or issues in input/output, message me on slack and I will update the details.

_________________________________________________________________________________________________STEPIK___________________________________________________________________________________________________

class TreePlay

{
   private:
      //Tree data structure here or create another class to implement it

   
   public:
      1. void insert(string s);         //inserts a new node to the tree

      2. void inOrder( );               //prints the in order traversal with each node separated by a space


      3. void levelOrder( );            //prints the level order traversal with each node separated by a             

                                          space


      4. void postOrderPalindrome( );   //prints the post order traversal with each node separated by a                                                  

                                         space printing only string palindromes

      5. int height( );                 //returns the height of the tree - if one root node - height is 1

      6. int search(string s);          //search string s in the tree, return 1 if found and 0 if not found.

      7. void deleteNode(string s);     //deletes the string s from the tree replacing s with successor node                                 

                                         if it has two children. If s is not present, don't do anything.

      8. void skipLevelOrder(int l);    //prints the level order traversal excluding the elements at level l 
                                        Root's level is 0 and if level is more than existing levels, don't 
                                        do anything.

};