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

Answer 1

#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(BSTNode *root, int key)

    {

        //check case 0, where root can be null or root is the key

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

            return root;

        //check case 1, where key is greater tha root's val

        if (root->val < key)

            return search(root->right, key);

        //check case 2, where key is less than root's val

        if (root->val > key)

            return search(root->left, key)

    }

    BSTNode *insert(BSTNode *root, int val)

    { // complete this method

        if(root==NULL) // check case 0 , where root is empty

    {

        treeNode *temp;

        temp=new treeNode;

        temp -> val = val;

        temp -> left = temp -> right = NULL;

        return temp;

    }

    if(val >(root->val))// check case 1 , where root val is less than val

    {

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

    }

    else if(val < (root->val))// check case 1 , where root val is greater than val

    {

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

    }

    /* Else there is nothing to do as the val is already in the tree. */

    return root;

    }

    bool remove(BSTNode *root, int val)

    { // complete this method

        BSTNode *temp;

        if (root == NULL)

        {

            cout << "Element Not Found";

        }

        else if (val < root->val)

        {

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

        }

        else if (val > root->val)

        {

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

        }

        else

        {

            /* Now We can remove this root and replace with either minimum element

        in the right sub tree or maximum element in the left subtree */

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

            {

                /* Here we will replace with minimum element in the right sub tree */

                temp = findMin(root->right);

                root->val = temp->val;

                /* As we replaced it with some other root, we have to removee that root */

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

            }

            else

            {

                /* If there is only one or zero children then we can directly

            remove it from the tree and connect its parent to its child */

                temp = root;

                if (root->left == NULL)

                    root = root->right;

                else if (root->right == NULL)

                    root = root->left;

                free(temp); /* temp is longer required */

            }

        }

        return true;

    

    }

private:

    void removeLeaf(BSTNode *root)

    { // complete this method

        if (root == NULL)// chech case 0, where root can be empty

            cout<<"there is no BST";

        if (root->left == NULL && root->right == NULL)// chech case 1, where root is the only data in BST

        {

            free(root);

            cout<<"there is only root in BST, hence removed";

        }

        // else recursively delete in left and right

        // subtrees.

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

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

        cout<<"Leaf Nodes Removed";

    }

    void removeNodeWithOneChild(BSTNode *root)

    { // complete this method

        if (root->left == NULL)

        {

            BSTNode  *temp = root->right;

            free(root);

            cout<<"Removed successfully";

        }

        else if (root->right == NULL)

        {

            BSTNode *temp = root->left;

            free(root);

            cout<<"Removed successfully";

        }

    }

    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);

        removee node;

    }

public:

    int getTreeHeight()

    {

        return getHeight(root);

    }

    void print()

    {

        print(root);

    }

    int getSize()

    {

        return size;

    }

};

#endif

----------summary------------

I assume your BSTNode data structure is like {

int val; ( if it is not 'val' then replace it with your keyword in above code )

BSTNode* left;

BSTNode* right

}