#include

using namespace std;

struct BinNode {

int key;

BinNode *left;

BinNode *right;

};

class myBST {

public:

myBST () { root = NULL; }

~myBST ();

BinNode* findInBST(int k); // return NULL if not found

void insertToBST(int k);

void preOrderTraversal();

void postOrderTraversal();

void inOrderTraversal();

void rotatedPrintTree();

private:

BinNode* root;

void free_helper(BinNode* node);

// BinNode* find_helper(BinNode* node, int k); //optional helper function for findInBST

// void insert_helper(BinNode* node, int k); //optional helper function for insertToBST

void preOrder(BinNode* node);

void postOrder(BinNode* node);

void inOrder(BinNode* node);

void rotatedPrint(BinNode* node, int d);

};

myBST::~myBST() {

free_helper(root);

}

void myBST::free_helper(BinNode* node) {

if(node != NULL) {

free_helper(node->left);

free_helper(node->right);

delete node;

}

}

// //***************************

// //recursive implementation***

// //***************************

// BinNode* myBST::findInBST(int k) {

// }

// BinNode* myBST::find_helper(BinNode* node, int k) {

// }

//*******************************

/on-recursive implementation***

//*******************************

BinNode* myBST::findInBST(int k) {

}

// //***************************

// //recursive implementation***

// //***************************

// void myBST::insertToBST(int k) {

// }

// void myBST::insert_helper(BinNode* node, int k) {

// }

//*******************************

/on-recursive implementation***

//*******************************

void myBST::insertToBST(int k) {

}

//***********************************

//preOrderTraversal implementation***

//***********************************

void myBST::preOrderTraversal() {

preOrder(root);

cout

}

void myBST::preOrder(BinNode* node) {

}

//************************************

//postOrderTraversal implementation***

//************************************

void myBST::postOrderTraversal() {

postOrder(root);

cout

}

void myBST::postOrder(BinNode* node) {

}

//**********************************

//inOrderTraversal implementation***

//**********************************

void myBST::inOrderTraversal() {

inOrder(root);

cout

}

void myBST::inOrder(BinNode* node) {

}

//***********************************

//print the tree (left rotated)******

//***********************************

void myBST::rotatedPrintTree() {

rotatedPrint(root, 0);

}

void myBST::rotatedPrint(BinNode* node, int d) {

if(node == NULL)

return;

if (node->right != NULL)

rotatedPrint(node->right, d+1);

for(int i = 0; i

cout

cout key

if (node->left != NULL)

rotatedPrint(node->left, d+1);

}

int main()

{

myBST testTree;

int user_input = 0;

while (user_input != -1) {

cout

cout

cout

cin >> user_input;

if (user_input >= 0 and user_input

testTree.insertToBST(user_input);

else if (user_input != -1)

cout

}

cout

testTree.rotatedPrintTree();

cout

testTree.preOrderTraversal();

cout

testTree.postOrderTraversal();

cout

testTree.inOrderTraversal();

user_input = 0;

while (user_input != -1) {

cout

cout

cout

cin >> user_input;

if (user_input >= 0 and user_input

BinNode* temp = testTree.findInBST(user_input);

if(temp == NULL)

cout

else {

cout

if(temp->left != NULL)

cout left->key

if(temp->right != NULL)

cout right->key

}

}

else if (user_input != -1)

cout

}

return 0;

}

In this assignment, you are asked to implement several functions in a Binary Search Tree (BST) class, called myBST, in bst.cpp. 1. Implement the public function findInBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function find helper () may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 2. Implement the public function insertToBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function insert_helper ) may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 3. Implement the private functions preOrder , postOrder (), and inOrder ) which are used to implement public functions preOrderTraversal (), postOrderTraversal (), and inOrderTraversal ), respectively. preOrder, postorder, and inOrder should be recursive functions, and no loop should be used in them Bevond writing codes in this assignment (Just to think about, no submission or gradin The function rotatedPrintTree ( ) prints the BST in a "left-rotated" fashion, i.e., the root on the left and the leaves on the right. For example, 20 10 15 10 20 15 Read carefully the functions for printing the tree (left-rotated), and think about how this function works. Also, think about why we use this function to print the left-rotated tree. Think about writing a function to normally (not rotated) print an arbitrary tree. Which printing is easier to implement? In this assignment, you are asked to implement several functions in a Binary Search Tree (BST) class, called myBST, in bst.cpp. 1. Implement the public function findInBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function find helper () may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 2. Implement the public function insertToBST (). You can choose to do this using recursion or not. If you choose to use recursion, a helper private function insert_helper ) may be helpful. (non-recursive is the default; if you want to use recursion, you'll need to comment/ uncommented certain parts in the code.) 3. Implement the private functions preOrder , postOrder (), and inOrder ) which are used to implement public functions preOrderTraversal (), postOrderTraversal (), and inOrderTraversal ), respectively. preOrder, postorder, and inOrder should be recursive functions, and no loop should be used in them Bevond writing codes in this assignment (Just to think about, no submission or gradin The function rotatedPrintTree ( ) prints the BST in a "left-rotated" fashion, i.e., the root on the left and the leaves on the right. For example, 20 10 15 10 20 15 Read carefully the functions for printing the tree (left-rotated), and think about how this function works. Also, think about why we use this function to print the left-rotated tree. Think about writing a function to normally (not rotated) print an arbitrary tree. Which printing is easier to implement