Question
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
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
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started