Question

In C++, create a class to hold a set of strings called setTree. setTrees contain copies of the strings inserted so that the strings cannot be changed due to the fact that changing the strings inside the set could break the binary search tree. The strings are case sensitive.

TreeSet implements the following:

bool add(const string& s) -- add s to the set, if it's not already there. Return true if the set changed, false otherwise.

void clear() -- remove all elements from the set

bool contains(const string& s) const -- test whether or not s is in the set.

bool isEmpty() const -- test whether or not the set is empty

bool remove(const string& s) -- remove s from the set, if it was there. Return true if the set changed, false otherwise.

int size() const -- return the number of strings in set.

int toArray(string sa[]) const -- put the elements of the set into the array sa. Assume that sa has sufficient room (it's the client's responsibility to check). You can place the strings in any order you choose.

The class also includes a zero-argument constructor to create an empty set, a constructor that takes in an array of strings and its size (creating a set containing each element of the array), copy constructor, assignment operator, and destructor. The copy constructor and assignment operator make deep copies.

setTree implements the set using a binary search tree. The tree does not need to be balanced. The implementation of the tree node class is hidden from the client. There are no memory leaks.

Answer 1

Classes:

/*
 * TreeSetNode 
 * It represents the node inside the Binary Search Tree (BST)
 */
class TreeSetNode
{
public:
    string s;
    TreeSetNode *left; /* left child of the BST */
    TreeSetNode *right; /* right child of the BST */

    TreeSetNode(const string _s) {
        s = _s;
        left = nullptr;
        right = nullptr;
    }
};

class TreeSet
{
public:
    /* head points to the root of the BST*/
    TreeSetNode *head;
    /* _size represents the current number of nodes of the BST */
    int _size;

    TreeSet() {
        head = nullptr;
        _size = 0;
    }
    TreeSet(string s[] , int size) {
        head = nullptr;
        for(int i = 0 ; i < size; i++) {
            add(s[i]);
        }
        _size = size;
    }
    TreeSet(TreeSet &sTree) {
        _size = sTree._size;
        head = buildTree(sTree.head);
    }
    ~TreeSet() {
        clear();
    }
    TreeSetNode* buildTree(TreeSetNode *toCopyFrom) {
        if(toCopyFrom == nullptr) {
            return nullptr;
        }
        TreeSetNode *root = new TreeSetNode(toCopyFrom->s);
        root->left = buildTree(toCopyFrom->left);
        root->right = buildTree(toCopyFrom->right);
        return root;
    }
    bool add(const string& s , TreeSetNode *root) {
        if(root->s == s) {
            /*
             * If s is already present, we will return false as we would not change the set. 
             */
            return false;
        }
        if(root->s < s) {
            if(root->right == nullptr) {
                root->right = new TreeSetNode(s);
                _size++;
                return true;
            } else {
                return add(s , root->right);
            }
        } else {
            if(root->left == nullptr) {
                root->left = new TreeSetNode(s);
                _size++;
                return true;
            } else {
                return add(s , root->left);
            }
        }
    }
    /*
    *  add s to the set, if it's not already there. Return true if the set changed, false otherwise.
    * */
    bool add(const string& s) {
        if(head == nullptr) {
            head = new TreeSetNode(s);
            return true;
        }
        /*
         * overloaded function add(string, TreeSetNode*) 
         * will be called which would take care of addition 
         * of the string in the set.
         */
        return add(s , head);
    }
    void clear(TreeSetNode *root) {
        if(root == nullptr) {
            return ;
        }
        /*
        * We would delete a node's left subtree , then the right sub tree and then would free the node
        * */
        clear(root->left);
        clear(root->right);
        free(root); 
    }
    /*
     * remove all elements from the set
     * */
    void clear() {
        clear(head);
        head = nullptr;
        _size = 0;
    }
    
    bool contains(const string &s , TreeSetNode *root) const {
        if(root == nullptr) {
            return false;
        }
        if(root->s == s) {
            return true;
        } else if(root->s < s) {
            return contains(s , root->right);
        } else {
            return contains(s , root->left);
        }
    }

    /*
    * test whether or not s is in the set.
    * */
    bool contains(const string& s) const {
        return contains(s , head);
    }
    bool isEmpty() const {
        return (_size==0);
    }
    TreeSetNode* removeNode(const string& s , TreeSetNode *root) {
        if(root->s == s) {
            if(root->left == nullptr && root->right == nullptr) {
                free(root);
                _size--;
                return nullptr;
            } else if(root->left == nullptr) {
                return root->right;
            } else if(root->right == nullptr) {
                return root->left;
            } else {
                TreeSetNode *lt = root->left;
                while(lt->right != nullptr) {
                    lt = lt->right;
                }
                root->s = lt->s;
                lt->s = s;
                root->left = removeNode(s , root->left);
                return root;
            }
        } else if(root->s < s) {
            root->right = removeNode(s , root->right);
        } else {
            root->left = removeNode(s , root->left);
        }
        return root;
    }
    /*
    * remove s from the set, if it was there. Return true if the set changed, false otherwise.
    * */
    bool remove(const string& s)  {
        if(!contains(s)) {
            return false;
        }
        head = removeNode(s , head);
        return true;
    }
    int size() const {
        return _size;
    }
    void toArray(TreeSetNode *root , string sa[] , int &i) const {
        if(root == nullptr) {
            return ;
        }
        toArray(root->left , sa , i);
        sa[i++] = root->s;
        toArray(root->right , sa , i);
    }
    int toArray(string sa[]) const {
        int i = 0 ;
        toArray(head , sa , i);
        return _size;
    }
};

I had also written a main function to test some functionalities of the above class..

int main() {

    /* Test 1 */
    string arr[6] = {"akash" , "panda" , "aa" , "as" , "sss" , "err"};
    TreeSet s_tree(arr , 6);
    string s_tree_arr[6];
    int sz = s_tree.toArray(s_tree_arr);
    cout << "Printing the contents of the Set :" << endl; 
    for(int i=0 ; i < 6 ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    cout << "Removing panda from the set" << endl;
    bool removed = s_tree.remove("panda");
    cout << "Removed" << endl;
    cout << "Printing the contents of the Set Again:" << endl; 
    sz = s_tree.toArray(s_tree_arr);
    for(int i=0 ; i < sz ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    cout << "Making use of the copy constructor" << endl;
    TreeSet new_stree = s_tree;
    sz = new_stree.toArray(s_tree_arr);
    cout << "Printing the contents of the new set:" << endl; 
    for(int i=0 ; i < sz ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    return 0;
}

The complete file of the class along with the main function is given below:
Paste the below mentioned conents to settree.cpp file.

#include<bits/stdc++.h>
using namespace std;

/*
 * TreeSetNode 
 * It represents the node inside the Binary Search Tree (BST)
 */
class TreeSetNode
{
public:
    string s;
    TreeSetNode *left; /* left child of the BST */
    TreeSetNode *right; /* right child of the BST */

    TreeSetNode(const string _s) {
        s = _s;
        left = nullptr;
        right = nullptr;
    }
};

class TreeSet
{
public:
    /* head points to the root of the BST*/
    TreeSetNode *head;
    /* _size represents the current number of nodes of the BST */
    int _size;

    TreeSet() {
        head = nullptr;
        _size = 0;
    }
    TreeSet(string s[] , int size) {
        head = nullptr;
        for(int i = 0 ; i < size; i++) {
            add(s[i]);
        }
        _size = size;
    }
    TreeSet(TreeSet &sTree) {
        _size = sTree._size;
        head = buildTree(sTree.head);
    }
    ~TreeSet() {
        clear();
    }
    TreeSetNode* buildTree(TreeSetNode *toCopyFrom) {
        if(toCopyFrom == nullptr) {
            return nullptr;
        }
        TreeSetNode *root = new TreeSetNode(toCopyFrom->s);
        root->left = buildTree(toCopyFrom->left);
        root->right = buildTree(toCopyFrom->right);
        return root;
    }
    bool add(const string& s , TreeSetNode *root) {
        if(root->s == s) {
            /*
             * If s is already present, we will return false as we would not change the set. 
             */
            return false;
        }
        if(root->s < s) {
            if(root->right == nullptr) {
                root->right = new TreeSetNode(s);
                _size++;
                return true;
            } else {
                return add(s , root->right);
            }
        } else {
            if(root->left == nullptr) {
                root->left = new TreeSetNode(s);
                _size++;
                return true;
            } else {
                return add(s , root->left);
            }
        }
    }
    /*
    *  add s to the set, if it's not already there. Return true if the set changed, false otherwise.
    * */
    bool add(const string& s) {
        if(head == nullptr) {
            head = new TreeSetNode(s);
            return true;
        }
        /*
         * overloaded function add(string, TreeSetNode*) 
         * will be called which would take care of addition 
         * of the string in the set.
         */
        return add(s , head);
    }
    void clear(TreeSetNode *root) {
        if(root == nullptr) {
            return ;
        }
        /*
        * We would delete a node's left subtree , then the right sub tree and then would free the node
        * */
        clear(root->left);
        clear(root->right);
        free(root); 
    }
    /*
     * remove all elements from the set
     * */
    void clear() {
        clear(head);
        head = nullptr;
        _size = 0;
    }
    
    bool contains(const string &s , TreeSetNode *root) const {
        if(root == nullptr) {
            return false;
        }
        if(root->s == s) {
            return true;
        } else if(root->s < s) {
            return contains(s , root->right);
        } else {
            return contains(s , root->left);
        }
    }

    /*
    * test whether or not s is in the set.
    * */
    bool contains(const string& s) const {
        return contains(s , head);
    }
    bool isEmpty() const {
        return (_size==0);
    }
    TreeSetNode* removeNode(const string& s , TreeSetNode *root) {
        if(root->s == s) {
            if(root->left == nullptr && root->right == nullptr) {
                free(root);
                _size--;
                return nullptr;
            } else if(root->left == nullptr) {
                return root->right;
            } else if(root->right == nullptr) {
                return root->left;
            } else {
                TreeSetNode *lt = root->left;
                while(lt->right != nullptr) {
                    lt = lt->right;
                }
                root->s = lt->s;
                lt->s = s;
                root->left = removeNode(s , root->left);
                return root;
            }
        } else if(root->s < s) {
            root->right = removeNode(s , root->right);
        } else {
            root->left = removeNode(s , root->left);
        }
        return root;
    }
    /*
    * remove s from the set, if it was there. Return true if the set changed, false otherwise.
    * */
    bool remove(const string& s)  {
        if(!contains(s)) {
            return false;
        }
        head = removeNode(s , head);
        return true;
    }
    int size() const {
        return _size;
    }
    void toArray(TreeSetNode *root , string sa[] , int &i) const {
        if(root == nullptr) {
            return ;
        }
        toArray(root->left , sa , i);
        sa[i++] = root->s;
        toArray(root->right , sa , i);
    }
    int toArray(string sa[]) const {
        int i = 0 ;
        toArray(head , sa , i);
        return _size;
    }
};

int main() {

    /* Test 1 */
    string arr[6] = {"akash" , "panda" , "aa" , "as" , "sss" , "err"};
    TreeSet s_tree(arr , 6);
    string s_tree_arr[6];
    int sz = s_tree.toArray(s_tree_arr);
    cout << "Printing the contents of the Set :" << endl; 
    for(int i=0 ; i < 6 ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    cout << "Removing panda from the set" << endl;
    bool removed = s_tree.remove("panda");
    cout << "Removed" << endl;
    cout << "Printing the contents of the Set Again:" << endl; 
    sz = s_tree.toArray(s_tree_arr);
    for(int i=0 ; i < sz ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    cout << "Making use of the copy constructor" << endl;
    TreeSet new_stree = s_tree;
    sz = new_stree.toArray(s_tree_arr);
    cout << "Printing the contents of the new set:" << endl; 
    for(int i=0 ; i < sz ; i++) {
        cout << s_tree_arr[i] << endl;
    }
    cout << "------------------------------------" << endl;
    return 0;
}

Steps to Compile:
g++ settree.cpp -o settree.out

How to run:
./settree.out

Sample output:

Printing the contents of the Set :
aa
akash
as
err
panda
sss
------------------------------------
Removing panda from the set
Removed
Printing the contents of the Set Again:
aa
akash
as
err
sss
------------------------------------
Making use of the copy constructor
Printing the contents of the new set:
aa
akash
as
err
sss
------------------------------------