Question

In C++, dealing with Binary Search trees. Implement search, insert, removeLeaf, and removeNodeWithOneChild methods in BST.h. BST.h code below

#include <iostream>
#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

This is the expected output

****************** Test BST Correctness ******************
Inserting the following numbers: [11, 12, 15, 17, 12, 19, 4, 5, 11, 19, 20, 32, 77, 65, 66, 88, 99, 10, 8, 19,
15, 66, 11, 19]
*** BST Structure (after insertion) ***
<11, null> <4, 11> <5, 4> <10, 5> <8, 10> <12, 11> <15, 12> <17, 15> <19, 17> <20, 19> <32, 20> <77,
32> <65, 77> <66, 65> <88, 77> <99, 88>
Size of BST: 16
*** Searching BST ***
Found: [19, 12, 4, 5, 19, 20, 32, 99, 8, 12]
Did not find: [29, 3, 27, 34, 45, 37, 25, 25, 24, 16]
*** Deleting BST ***
Deleted: [12, 15, 5, 17, 19, 4, 20, 32, 99, 10, 8]
Did not find: [16, 5, 19, 17, 19, 39, 19, 15, 21]
*** BST Structure (after deletion) ***
<11, null> <77, 11> <65, 77> <66, 65> <88, 77>
Size of BST: 5
****************** Clean up ******************
Size of hash table: 0
Size of BST: 0

Answer 1

Implementation of the methods: 

BSTNode *search(int key) {

        if (root == NULL || root->key == key)

           return root;

        if (root->key < key)

          return search(root->right, key);

       return search(root->left, key);

}

BSTNode *insert(int val) {

     if(!root)

    {

        return new BST(value);

    }

    if(value > root->data)

    {

        root->right = Insert(root->right, value);

    }

    else

    {

root->left = Insert(root->left, value);

    }

    return root;

}
bool remove(int key) {

    if (root == NULL) return false;

    if (key < root->key)

        root->left = remove(root->left, key);

    else if (key > root->key)

        root->right = remove(root->right, key);

    else

    {

if (root->left == NULL)

        {

            struct node *temp = root->right;

            free(root);

            return true;

        }

        else if (root->right == NULL)

        {

            struct node *temp = root->left;

            free(root);

            return temp;

        }

        struct node* temp = minValueNode(root->right);

        root->key = temp->key;

        root->right = remove(root->right, temp->key);

    }

    return false;

 }

void removeNodeWithOneChild(BSTNode *node) {

if (root==NULL)

        return NULL;

    root->left = removeNodeWithOneChild(root->left);

    root->right = removeNodeWithOneChild(root->right);

    if (root->left==NULL && root->right==NULL)

        return root;

    if (root->left==NULL)

    {

        BSTNode *new_root = root->right;

        free(root);

        return new_root;

    }

    if (root->right==NULL)

    {

        BSTNode *new_root = root->left;

        free(root);

        return new_root;

    }

    return root;

}