Question

In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h. BST.h code below. CPP code also provided for reference, nothing to be changed on cpp code.

#include 
#include "BSTNode.h"
using namespace std;

#ifndef BST_H_
#define BST_H_

class BST {

public:

        BSTNode *root;
        int size;

        BST() {
                root = NULL;
                size = 0;
        }

        ~BST() {
                if (root != NULL)
                        deepClean(root);
        }

        BSTNode *search(int key) { // complete this method
        }

        BSTNode *insert(int val) { // complete this method
        }

        bool remove(int val) { // complete this method
        }

private:

        void removeLeaf(BSTNode *leaf) { // complete this method
        }

        void removeNodeWithOneChild(BSTNode *node) { // complete this method
        }

        static BSTNode *findMin(BSTNode *node) {
                if (NULL == node)
                        return NULL;
                while (node->left != NULL) {
                        node = node->left;
                }
                return node;
        }

        static BSTNode *findMax(BSTNode *node) {
                if (NULL == node)
                        return NULL;
                while (node->right != NULL) {
                        node = node->right;
                }
                return node;
        }

        void print(BSTNode *node) {
                if (NULL != node) {
                        node->toString();
                        cout << " ";
                        print(node->left);
                        print(node->right);
                }
        }

        static int getHeight(BSTNode *node) {
                if (node == NULL)
                        return 0;
                else
                        return 1 + max(getHeight(node->left), getHeight(node->right));
        }
    
    static void deepClean(BSTNode *node) {
        if (node->left != NULL)
            deepClean(node->left);
        if (node->right != NULL)
            deepClean(node->right);
        delete node;
    }

public:

        int getTreeHeight() {
                return getHeight(root);
        }

        void print() {
                print(root);
        }

        int getSize() {
                return size;
        }
};

#endif

testCorrectness.cpp
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#include "BST.h"
#include "Hashing.h"
using namespace std;

int arrayIns[] = { 11, 12, 15, 17, 12, 19, 4, 5, 11, 19, 20, 32, 77, 65, 66, 88,
                99, 10, 8, 19, 15, 66, 11, 19 };
const int numInsert = sizeof(arrayIns) / sizeof(int);

int searchArray[] = { 29, 3, 19, 27, 12, 34, 4, 5, 19, 20, 32, 45, 37, 25, 99,
                25, 8, 24, 12, 16 };
const int numSearch = sizeof(searchArray) / sizeof(int);

int deleteArray[] = { 16, 12, 15, 5, 17, 19, 4, 5, 19, 20, 32, 17, 19, 39, 99,
                10, 8, 19, 15, 21 };
const int numDelete = sizeof(deleteArray) / sizeof(int);

const int cleanUp[] = { 11, 77, 65, 66, 88 };
const int numCleanUp = sizeof(cleanUp) / sizeof(int);

const int TABLE_SIZE = 7;

void printArray(int *A, int len) {
        if (0 == len)
                cout << "[]";
        else {
                cout << "[";
                for (int i = 0; i < len - 1; i++) {
                        if (A[i] == INT_MAX)
                                cout << "infty, ";
                        else
                                cout << A[i] << ", ";
                }
                if (A[len - 1] == INT_MAX)
                        cout << "infty]";
                else
                        cout << A[len - 1] << "]";
                cout << endl;
        }
}

void printList(list &A) {
        if (0 == A.size())
                cout << "[]" << endl;
        else {
                list::iterator it;
                cout << "[";
                for (it = A.begin(); next(it) != A.end(); ++it)
                        cout << *it << ", ";
                cout << *it << "]";
                cout << endl;
        }
}

void printList(list *A) {
        if (0 == A->size())
                cout << "[]" << endl;
        else {
                list::iterator it;
                cout << "[";
                for (it = A->begin(); next(it) != A->end(); ++it)
                        cout << *it << ", ";
                cout << *it << "]";
                cout << endl;
        }
}

//HASHING -------------------------------------------
Hashing *testHashing() {
        cout << "****************** Test Hashing Correctness ******************"
                        << endl << endl;
        Hashing *hChain = new Hashing(TABLE_SIZE);

        cout << "Inserting the following numbers: ";
        printArray(arrayIns, numInsert);

        for (int i = 0; i < numInsert; i++) {
                hChain->insert(arrayIns[i]);
        }

        cout << endl << "*** Hash Table Structure (after insertion) ***" << endl;
        int size = 0;
        for (int i = 0; i < TABLE_SIZE; i++) {
                cout << "Slot " << i << ": ";
                printList(hChain->getList(i));
                size += hChain->getList(i)->size();
        }
        cout << endl << "Size of hash table: " << size << endl;

        cout << "\n*** Searching Hash Table ***" << endl;
        list foundList;
        list notFoundList;

        for (int i = 0; i < numSearch; i++) {
                int val = searchArray[i];
                bool found = hChain->search(val);
                if (found)
                        foundList.push_back(val);
                else
                        notFoundList.push_back(val);
        }
        cout << "Found: ";
        printList(foundList);
        cout << "Did not find: ";
        printList(notFoundList);
        cout << endl << "*** Deleting Hash Table ***" << endl;

        list deleteList;
        list deleteNotFoundList;
        for (int i = 0; i < numDelete; i++) {
                int val = deleteArray[i];
                bool deleted = hChain->remove(val);
                if (deleted)
                        deleteList.push_back(val);
                else
                        deleteNotFoundList.push_back(val);
        }
        cout << "Deleted: ";
        printList(deleteList);
        cout << "Did not find: ";
        printList(deleteNotFoundList);

        cout << endl << "*** Hash Table Structure (after deletion) ***" << endl;
        size = 0;
        for (int i = 0; i < TABLE_SIZE; i++) {
                cout << "Slot " << i << ": ";
                printList(hChain->getList(i));
                size += hChain->getList(i)->size();
        }
        cout << endl << "Size of hash table: " << size << endl;
        return hChain;
}

//BST
BST *testBST() {
        cout << "\n****************** Test BST Correctness ******************"
                        << endl << endl;

        BST *bst = new BST();
        cout << "Inserting the following numbers: ";
        printArray(arrayIns, numInsert);

        for (int i = 0; i < numInsert; i++) {
                bst->insert(arrayIns[i]);
        }

        cout << endl << "*** BST Structure (after insertion) ***" << endl;
        bst->print();
        cout << endl << endl << "Size of BST: " << bst->getSize() << endl;

        cout << "\n*** Searching BST ***" << endl;
        list foundList;
        list notFoundList;

        for (int i = 0; i < numSearch; i++) {
                int val = searchArray[i];
                if (bst->search(val) != NULL)
                        foundList.push_back(val);
                else
                        notFoundList.push_back(val);
        }
        cout << "Found: ";
        printList(foundList);
        cout << "Did not find: ";
        printList(notFoundList);
        cout << endl << "*** Deleting BST ***" << endl;

        list deleteList;
        list deleteNotFoundList;
        for (int i = 0; i < numDelete; i++) {
                int val = deleteArray[i];
                bool deleted = bst->remove(val);
                if (deleted)
                        deleteList.push_back(val);
                else
                        deleteNotFoundList.push_back(val);
        }
        cout << "Deleted: ";
        printList(deleteList);
        cout << "Did not find: ";
        printList(deleteNotFoundList);

        cout << endl << "*** BST Structure (after deletion) ***" << endl;
        bst->print();
        cout << endl << endl << "Size of BST: " << bst->getSize() << endl;
        return bst;
}

static void cleanTest(Hashing *hashing, BST *bst) {
        cout << "\n****************** Clean up ******************" << endl;
        for (int i = 0; i < numCleanUp; i++) {
                hashing->remove(cleanUp[i]);
                bst->remove(cleanUp[i]);
        }
        int size = 0;
        for (int i = 0; i < TABLE_SIZE; i++)
                size += hashing->getList(i)->size();

        cout << "\nSize of hash table: " << size << endl;
        cout << "Size of BST: " << bst->getSize();
        delete hashing;
        delete bst;
}

int main() {
        cleanTest(testHashing(), testBST());
        return 0;
}

BSTnode.h

#include <iostream>
using namespace std;

#ifndef BSTNODE_H_
#define BSTNODE_H_

class BSTNode {

public:

        int value;
        BSTNode *left, *right, *parent;

        BSTNode(int val) {
                // each node is inserted as a leaf
                value = val;
                left = NULL;
                right = NULL;
                parent = NULL;
        }

        void toString() {
                if (parent == NULL)
                        cout << "<" << value << ", null>";
                else
                        cout << "<" << value << ", " << parent->value << ">";
        }
};

#endif

Answer 1

Implemented all the functions asked.. Do tell me in comments if you have any doubt and if the solution is helpful, pls do upvote!!!

*****************************************

Code-

BSTNode* removeNodeWithOneChild_helper(BSTNode* root, BSTNode* node){
if(root==NULL){
return NULL;
}
  
if(root->data==node->data){
if (root->left!=NULL){
root->left=NULL;
}
if(root->right!=NULL){
root->right=NULL;
}
  
}
  
if(root->data<node->data){
root->right=removeNodeWithOneChild_helper(root->right,node);
}
  
else{
root->left=removeNodeWithOneChild_helper(root->left,node);
}
  
return root;
  
  
  
}

void removeNodeWithOneChild(BSTNode *node){
  
  
removeNodeWithOneChild_helper(root,node);
  
}

BSTNode* removeLeaf_helper(BSTNode* root,BSTNode* leaf){
  
if(root==NULL){
return NULL;
}
  
if(root->data==leaf->data && root->left==NULL && root->right==NULL){
return NULL;
}
  
  
if(leaf->data<root->data){
root->left=removeLeaf_helper(root->left,leaf);
  
  
}
  
else{
root->right=removeLeaf_helper(root->right,leaf);
}
  
return root;
}

void removeLeaf(BSTNode* leaf){
  
removeLeaf_helper(root,leaf);
  
}

BSTNode* insert_helper(BSTNode* root,int val){

if(root==NULL){
BSTNode* new_node=new BSTNode(val);
return new_node;
}
  
  
else{
if(root->data==val){
return root;
}
else if(root->data<val){
root->right=insert_helper(root->right,val);
}else{
root->left=insert_helper(root->left,val);
}
}
return root;

}

BSTNode* insert(int val){
return insert_helper(root,val);
}

BSTNode* search_helper(BSTNode* root,int key){
  
if(root==NULL){
return root;
}
  
if(root->data==key){
return root;
}
  
if(key<root->data){
return search_helper(root->left,key);
}
  
return search_helper(root->right,key);
}

BSTNode* search(int key){
  
return search_helper(root,key);
  
}