Question

Can someone please help me with the following:

Implement a Binary Search Tree that can be used to
store data values that are strings.  The data values
will be stored in nodes in a binary search tree. 
Each node will have a unique integer key.

Provide functions to add, get and remove elements
to/from the tree.

Also provide functions to print the elements (both the
key and the data values) in forward (dump) and reverse
(dump_rev) order.  To help in debugging/verifying your
program, 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 to
see what your program should output.

NOTES:

If your add functions discovers that a node already exists
at that key, simply update the data stored at that node.

It is possible to implement the get function recursively or
not.  Since this program is fairly short, I want you to go ahead
and implement two different get functions.  One recursive
and the other not.  See the "main" test program below to
see what to name them and what command to associate with
them.

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 out
parts 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= five
MAIN: cmd= dump, key= 0, v= 0
    DUMP: (root node = 5)
    DUMP: key= 5, data = five, level = 1

MAIN: cmd= add, key= 8, v= eight
MAIN: 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 = 2

MAIN: cmd= add, key= 6, v= six
MAIN: 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 = 6

MAIN: cmd= add, key= 4, v= four
MAIN: 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 = 6

MAIN: 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 = 2

MAIN: cmd= add, key= 8, v= EIGHT
PUT:  updating existing node
MAIN: 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 = 6

MAIN: cmd= get, key= 6, v= 6
  GET: examining node(s):  five EIGHT six
MAIN: get returns: six
MAIN: cmd= get, key= 9, v= 9
  GET: examining node(s):  five EIGHT
MAIN: get returns: GET: not found
MAIN: cmd= rem, key= 9, v= 9
REMOVE: item not found.
MAIN: cmd= rem, key= 8, v= 8
MAIN: 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 = 2

MAIN: cmd= rem, key= 4, v= 4
MAIN: 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 = 2

MAIN: cmd= quit, key= 0, v= 0
============================================================

Answer 1

I have implemented all the functions that are to be done in the above code. Also added comments in the code.

Note: You may look the screenshot of the code to have better understanding of the indentation.

C++ Code:

#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;
}

//code added
node* insertNode(node* root, int k, string s)
{
//check if empty tree
if(!root)
return new node(k,s);

//check if key already present
if(root->key == k)
{
//update value
root->value = s;
return root;
}

//else traverse to right position of insertion
if(k < root->key)
root->left = insertNode(root->left,k,s);
else if(k > root->key)
root->right = insertNode(root->right,k,s);

return root;
}

void add(int k, string s)
{
//code
root = insertNode(root,k,s);
}

//rdump function to traverse in ascending order
void rdump(node* root, int lev)
{
if(!root)
{
return;
}
else
{
rdump(root->left,lev+1);
//print data
cout<<"DUMP:key="<<root->key<<", data="<<root->value;
cout<<", level="<<lev;
//check for left child
if(root->left)
cout<<", lcld="<<root->left->key;
//check right child
if(root->right)
cout<<", rcld="<<root->right->key;
cout<<endl;
rdump(root->right,lev+1);
}
}

void dump()
{
//dump calls the following recursive function rdump
//rdump(root, 1);
//print root node
if(!root)
{
cout<<"Empty tree\n";
return;
}
else
{
cout<<"DUMP:(root node="<<root->key<<")"<<endl;
//call recursive function to traverse inorder(ascending)
rdump(root,1);
}
}

//rdump_rev function to traverse in descending order
void rdump_rev(node* root, int lev)
{
if(!root)
{
return;
}
else
{
rdump(root->right,lev+1);
//print data
cout<<"DUMP:key="<<root->key<<", data="<<root->value;
cout<<", level="<<lev;
//check for left child
if(root->left)
cout<<", lcld="<<root->left->key;
//check right child
if(root->right)
cout<<", rcld="<<root->right->key;
cout<<endl;
rdump(root->left,lev+1);
}
}

void dump_rev()
{
//print root node
if(!root)
{
cout<<"Empty tree\n";
return;
}
else
{
cout<<"DUMP:(root node="<<root->key<<")"<<endl;
//call recursive function to traverse inorder(ascending)
rdump_rev(root,1);
}
}

//search for key
string search_value_rec(node* root, int k)
{
if(!root)
return "Key not found.";
//key found
if(root->key == k)
return root->value;
//check left sub tree
if(root->key > k)
return search_value_rec(root->left,k);
//check right sub tree
else if(root->key < k)
return search_value_rec(root->right, k);
}

//changed return type from int to string to return the value of node
string recursive_get(int k)
{
//code
return search_value_rec(root,k);
}

//search for key
string search_value_itr(node* root, int k)
{
if(!root)
return "Key not found.";
//check in while loop
while(root != NULL)
{
//key found
if(root->key == k)
return root->value;

//go to left sub tree
if(k < root->key)
root = root->left;
//go to right sub tree
else if(k > root->key)
root = root->right;
}

//key not found
return "Key not found.";
}

//changed return type from int to string to return the value of node
string non_recursive_get(int k)
{
//code
return search_value_itr(root,k);
}

//get minimum key in right sub tree
node* minNode(node* root)
{
while(root && root->left)
root = root->left; //traverse left to get minimum
return root;
}

//delete node
node* deleteNode(node* root, int k)
{
//empty tree
if(!root)
return root;

//check left subtree
if(k < root->key)
root->left = deleteNode(root->left, k);
//check right sub tree
else if(k>root->key)
root->right = deleteNode(root->right, k);

//node to be deleted
else
{
//if only one child or no child
if(!root->left)
{
node* tmp = root->right;
delete root;
return tmp; //return right child
}
else if(!root->right)
{
node* tmp = root->left;
delete root;
return tmp; //return left child
}

//node with 2 children
//get the minimum key node in right subtree to replace
node* mini = minNode(root->right);

//copy its contents
root->key = mini->key;
root->value = mini->value;

//delete that replaced node
root->right = deleteNode(root->right,mini->key);
}
return root;
}

//remove node
void removeNode(int k)
{
//code
deleteNode(root,k);

}
};

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.removeNode(k);
}
else if (cmd == "quit") {
exit(0);
}
}
}
Output:

Screenshot of code: