In this programming assignment, you are supposed to implement a Binary Search Tree (BST). Each node of the BST will be a string. This data structure should implement the following methods:

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.

};

You are expected to write code for each of the functions as well as implement the BST. A sample int main() function that invokes your BST is provided and you can test it on three test cases. Make sure you do not change any code in the main() function.

Composition of main() Method (How I will Test your code):

Input:

9 - Line 1 indicates the number of operations you will be performing or the number of lines that follow

1 Cat - Each line's first integer indicates operation; 1 here means insert() and this follows input to the operation - "Cat"

1 DoD - insert(DoD)

2 - 2 is inOrder. Therefore, operation is inorder()

3 - 3 is levelOrder. Therefore, operation is levelOrder ()

4 - 4 is postOrderPalindrome. Therefore, operation is postOrderPalindrome()

5 - 5 is height. Therefore, operation is height()

6 Cat - 6 is search. Therefore, operation is search(Cat)

7 Cat - 7 is deleteNode. Therefore, operation is deleteNode(Cat)

8 1 - 8 is skipLevelOrder . Therefore, operation is skipLevelOrder(1)

Output (for above input):

Functions 1, 5, 6 and 7 do not print anything.

Cat DoD

Cat DoD

DoD

2

1

DoD

#include #include #include using namespace std;

class TreePlay { private: // Tree data structure here public: void insert(string s); void inOrder(); void levelOrder( ); void postOrderPalindrome( ); int height( ); int search(string s); void deleteNode(string s); void skipLevelOrder(int l); };

int main() { //DO NOT CHANGE THIS FUNCTION. CHANGE YOUR IMPLEMENTATION CODE TO MAKE IT WORK int noOfLines, operation, inputInt, h; string input; cin>>noOfLines; TreePlay obj; for(int i=0;i>operation; switch(operation) { case 1: cin>>input; obj.insert(input); break; case 2: obj.inOrder(); cout<<" "; break; case 3: obj.levelOrder(); cout<<" "; break; case 4: obj.postOrderPalindrome(); cout<<" "; break; case 5: h=obj.height(); cout<>input; h=obj.search(input); cout<>input; obj.deleteNode(input); break; case 8: cin>>inputInt; obj.skipLevelOrder(inputInt); cout<<" "; break; } } return 0; }