Can someone please help me with the following:
Implement a Binary Search Tree that can be used tostore data values that are strings. The data valueswill be stored in nodes in a binary search tree. Each node will have a unique integer key.Provide functions to add, get and remove elementsto/from the tree.Also provide functions to print the elements (both thekey and the data values) in forward (dump) and reverse(dump_rev) order. To help in debugging/verifying yourprogram, have these functions also print out the following: 0) key and data value of current node 1) key of the node’s left child (if it exists) 2) key of the node’s right child (if it exists) 3) the level of the node being printed.This will remove any ambiguity as to the structure of the tree at any time. See the sample output below tosee what your program should output.NOTES:If your add functions discovers that a node already existsat that key, simply update the data stored at that node.It is possible to implement the get function recursively ornot. Since this program is fairly short, I want you to go aheadand implement two different get functions. One recursiveand the other not. See the “main” test program below tosee what to name them and what command to associate withthem.SIMPLIFYING ASSUMPTIONS: We will not remove the root node or any branch node with two children.Here is some code to give you a head start:Do not modify the given code, except perhaps to temporarily comment outparts of it that you have not yet supported.============================================================#include <iostream>#include <cstdlib>#include <string>using namespace std;class node {public: int key; string value; node* left; node* right; node(int k, string v) { key = k; value = v; left = NULL; right = NULL; }};class bst {private: node* root;public: bst() { root = NULL; } void add(int k, string s) { //code } void dump() { //dump calls the following recursive function rdump //rdump(root, 1); } void dump_rev() { //code } int recursive_get(int k) { //code } int non_recursive_get(int k) { //code } void remove(int k) { //code }};int main(void){ bst mybst; string cmd; int k; string v; while (cin >> cmd >> k >> v) { cout << “MAIN: cmd= ” << cmd << “, key= ” << k << “, v= ” << v << endl; if (cmd == “add”) { mybst.add(k, v); } else if (cmd == “dump”) { // traverse tree in ascending order mybst.dump(); } else if (cmd == “dump_rev”) { // traverse tree in descending order mybst.dump_rev(); } else if (cmd == “get”) { v = mybst.non_recursive_get(k); cout << “MAIN: get returns: ” << v << endl; } else if (cmd == “rget”) { v = mybst.recursive_get(k); cout << “MAIN: rget returns: ” << v << endl; } else if (cmd == “rem”) { mybst.remove(k); } else if (cmd == “quit”) { exit(0); } }}== Sample output ===========================================MAIN: cmd= add, key= 5, v= fiveMAIN: cmd= dump, key= 0, v= 0 DUMP: (root node = 5) DUMP: key= 5, data = five, level = 1MAIN: cmd= add, key= 8, v= eightMAIN: cmd= dump, key= 0, v= 0 DUMP: (root node = 5) DUMP: key= 5, data = five, level = 1, rcld = 8 DUMP: key= 8, data = eight, level = 2MAIN: cmd= add, key= 6, v= sixMAIN: cmd= dump, key= 0, v= 0 DUMP: (root node = 5) DUMP: key= 5, data = five, level = 1, rcld = 8 DUMP: key= 6, data = six, level = 3 DUMP: key= 8, data = eight, level = 2, lcld = 6MAIN: cmd= add, key= 4, v= fourMAIN: cmd= dump, key= 9, v= 9 DUMP: (root node = 5) DUMP: key= 4, data = four, level = 2 DUMP: key= 5, data = five, level = 1, lcld = 4, rcld = 8 DUMP: key= 6, data = six, level = 3 DUMP: key= 8, data = eight, level = 2, lcld = 6MAIN: cmd= dump_rev, key= 0, v= 0 DUMP: (root node = 5) DUMP: key= 8, data = eight, level = 2, lcld = 6 DUMP: key= 6, data = six, level = 3 DUMP: key= 5, data = five, level = 1, lcld = 4, rcld = 8 DUMP: key= 4, data = four, level = 2MAIN: cmd= add, key= 8, v= EIGHTPUT: updating existing nodeMAIN: cmd= dump, key= 9, v= 9 DUMP: (root node = 5) DUMP: key= 4, data = four, level = 2 DUMP: key= 5, data = five, level = 1, lcld = 4, rcld = 8 DUMP: key= 6, data = six, level = 3 DUMP: key= 8, data = EIGHT, level = 2, lcld = 6MAIN: cmd= get, key= 6, v= 6 GET: examining node(s): five EIGHT sixMAIN: get returns: sixMAIN: cmd= get, key= 9, v= 9 GET: examining node(s): five EIGHTMAIN: get returns: GET: not foundMAIN: cmd= rem, key= 9, v= 9REMOVE: item not found.MAIN: cmd= rem, key= 8, v= 8MAIN: cmd= dump, key= 9, v= 9 DUMP: (root node = 5) DUMP: key= 4, data = four, level = 2 DUMP: key= 5, data = five, level = 1, lcld = 4, rcld = 6 DUMP: key= 6, data = six, level = 2MAIN: cmd= rem, key= 4, v= 4MAIN: cmd= dump, key= 9, v= 9 DUMP: (root node = 5) DUMP: key= 5, data = five, level = 1, rcld = 6 DUMP: key= 6, data = six, level = 2MAIN: cmd= quit, key= 0, v= 0============================================================
Expert Answer
Answer to Can someone please help me with the following: Implement a Binary Search Tree that can be used to store data values that…