Поиск элемента в бинарном дереве

#include<iostream>
#include<set>
#include<algorithm>
#include <numeric>
using namespace std;
int main()
{
    set<double> sd{ 1,2,3,4,15,26,37,77,88,99.999 };// :D
    double sum = accumulate(sd.begin(), sd.end(), 0);
    double average_d = sum / sd.size();
    cout << sum << ' ' << average_d  << endl;
    set<double>::iterator it_lover = lower_bound(sd.begin(), sd.end(), average_d);
    set<double>::iterator it_upper = upper_bound(sd.begin(), sd.end(), average_d);
    cout << *it_lover << ' ' << *it_upper << ' ' <<average_d << endl;
    return 0;
}

#include <iostream>
#include <cstdlib>
#include <windows.h>
#include <string>
 
using namespace std;
 
class BST
{
private:
    struct node
    {
        int key;
        string data;
        node* left;
        node* right;
    };
    node* root;
 
    node* CreateLeaf(int key, string data); // создать элемент
    void AddLeafPrivate(int key, string data, node* Ptr);
    void PrintInOrderPrivate(node* Ptr);
    node* ReturnNodePrivate(int key, node* Ptr);
    node* FindSmallestPrivate(node* Ptr);
    void RemoveNodePrivate(int key, node* parent);
    void RemoveRootMatch();
    void RemoveMatch(node* parent, node* match, bool left);
 
public:
    BST(); // конструктор
    void AddLeaf(int key, string data); // добавить элемент
    void PrintInOrder(); // вывести дерево на экран
    void ReturnNode(int key);
    node* FindSmallest();
    void RemoveNode(int key);
};
 
BST::BST()
{
    root = NULL;
}
 
BST::node* BST::CreateLeaf(int key, string data)
{
    node* n = new node;
    n->key = key;
    n->data = data;
    n->left = NULL;
    n->right = NULL;
 
    return n;
}
 
void BST::AddLeaf(int key, string data)
{
    AddLeafPrivate(key, data, root);
}
 
void BST::AddLeafPrivate(int key, string data, node* Ptr)
{
    if (root == NULL)
    {
        root = CreateLeaf(key, data);
    }
    else if (key < Ptr->key)
    {
        if (Ptr->left != NULL)
        {
            AddLeafPrivate(key, data, Ptr->left);
        }
        else
        {
            Ptr->left = CreateLeaf(key, data);
        }
    }
    else if (key > Ptr->key)
    {
        if (Ptr->right != NULL)
        {
            AddLeafPrivate(key, data, Ptr->right);
        }
        else
        {
            Ptr->right = CreateLeaf(key, data);
        }
    }
    else
    {
        cout << "Ключ уже существует" << endl;
    }
}
 
void BST::PrintInOrder()
{
    PrintInOrderPrivate(root);
}
 
void BST::PrintInOrderPrivate(node* Ptr)
{
    if (root != NULL)
    {
        if (Ptr->left != NULL)
        {
            PrintInOrderPrivate(Ptr->left);
        }
        cout << Ptr->key << " " << Ptr->data << endl;
        if (Ptr->right != NULL)
        {
            PrintInOrderPrivate(Ptr->right);
        }
    }
    else
    {
        cout << "Дерево не содержит данных" << endl;
    }
}
 
void BST::ReturnNode(int key)
{
    if (root != NULL)
    {
        node* n = ReturnNodePrivate(key, root);
        if (n != NULL)
        {
            cout << n->key << " " << n->data << endl;
        }
        else
        {
            cout << "Введенного вами ключа не существует" << endl;
        }
    }
    else
    {
        cout << "Дерево не содержит данных" << endl;
    }
}
 
BST::node* BST::ReturnNodePrivate(int key, node* Ptr)
{
    if (Ptr != NULL)
    {
        if (Ptr->key == key)
        {
            return Ptr;
        }
        if (key < Ptr->key)
        {
            return ReturnNodePrivate(key, Ptr->left);
        }
        if (key > Ptr-> key)
        {
            return ReturnNodePrivate(key, Ptr->right);
        }
    }
    else
    {
        return NULL;
    }
}
 
BST::node* BST::FindSmallest()
{
    return FindSmallestPrivate(root);
}
 
BST::node* BST::FindSmallestPrivate(node* Ptr)
{
    if (root != NULL)
    {
        if (Ptr->left != NULL)
        {
            return FindSmallestPrivate(Ptr->left);
        }
        else
        {
            return Ptr;
        }
    }
    else
    {
        cout << "Дерево не содержит данных" << endl;
        return NULL;
    }
}
 
void BST::RemoveNode(int key)
{
    RemoveNodePrivate(key, root);
}
 
void BST::RemoveNodePrivate(int key, node* parent)
{
    if (root != NULL)
    {
        if (root->key == key)
        {
            RemoveRootMatch();
        }
        else
        {
            if (key < parent->key && parent->left != NULL)
            {
                parent->left->key == key ?
                    RemoveMatch(parent, parent->left, true) :
                    RemoveNodePrivate(key, parent->left);
            }
            else if (key > parent->key && parent->right != NULL)
            {
                parent->right->key == key ?
                    RemoveMatch(parent, parent->right, false) :
                    RemoveNodePrivate(key, parent->right);
            }
            else
            {
                cout << "Значение не найдено" << endl;
            }
        }
    }
    else
    {
        cout << "Дерево не содержит данных" << endl;
    }
}
 
void BST::RemoveRootMatch()
{
    if (root != NULL)
    {
        node* smallestInRightSubtree = new node;
        int delKey;
        string delData;
 
        // У корня нет потомков
        if (root->left == NULL && root->right == NULL)
        {
            root = NULL;
        }
 
        // У корня один потомок
        else if (root->left == NULL && root->right != NULL)
        {
            root = root->right;
        }
        else if (root->left != NULL && root->right == NULL)
        {
            root = root->left;
        }
 
        // У корня два потомка
        else
        {
            smallestInRightSubtree = FindSmallestPrivate(root->right);
            delKey = smallestInRightSubtree->key;
            delData = smallestInRightSubtree->data;
            RemoveNodePrivate(smallestInRightSubtree->key, root);
            root->key = delKey;
            root->data = delData;
        }
    }
}
 
void BST::RemoveMatch(node* parent, node* match, bool left)
{
    if (root != NULL)
    {
        node* smallestInRightSubtree = new node;
        int delKey;
        string delData;
 
        // У элемента нет потомков
        if (match->left == NULL && match->right == NULL)
        {
            left == true ? parent->left = NULL : parent->right = NULL;
            delete match;
        }
 
        // У элемента один потомок
        else if (match->left == NULL && match->right != NULL)
        {
            left == true ? parent->left = match->right : parent->right = match->right;
            match->right = NULL;
            delete match;
        }
        else if (match->left != NULL && match->right == NULL)
        {
            left == true ? parent->left = match->left : parent->right = match->left;
            match->left = NULL;
            delete match;
        }
 
        // У элемента два потомка
        else
        {
            smallestInRightSubtree = FindSmallestPrivate(match->right);
            delKey = smallestInRightSubtree->key;
            delData = smallestInRightSubtree->data;
            RemoveNodePrivate(smallestInRightSubtree->key, root);
            match->key = delKey;
            match->data = delData;
        }
    }
    else
    {
        cout << "Дерево не содержит данных" << endl;
    }
}
 
void main()
{
 
    setlocale(LC_ALL, "Russian");
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
 
    BST myTree;
 
    myTree.AddLeaf(50, "lera");
    myTree.AddLeaf(40, "masha");
    myTree.AddLeaf(60, "ksu");
    myTree.AddLeaf(20, "vadim");
    myTree.AddLeaf(45, "alena");
    myTree.AddLeaf(55, "egor");
    myTree.AddLeaf(65, "nataly");
 
    myTree.PrintInOrder();
    cout << endl;
 
    myTree.ReturnNode(15);
    cout << endl;
 
    myTree.ReturnNode(50);
    cout << endl;
 
    myTree.RemoveNode(40);
    myTree.RemoveNode(50);
 
    myTree.PrintInOrder();
    cout << endl;
}

BST::node* BST::FindSmallest()
{
    if (!root)
        return nullptr;
 
    auto *p = root;
    while(p->left)
        p = p->left;
 
    return p;
}

BST::node* LowerBound(int key, BST::node &node)
{
    if (node.key < key)
    {
        if (!node.right)
            return &node;
 
        auto *p = LowerBound(key, *node.right);
        return p? p: &node;
    }
    
    if (node.key > key && node.left)
        return LowerBound(key, *node.left);
 
    return nullptr;
}
 
BST::node* BST::LowerBound(int key)
{
    return root? LowerBound(key, *root): nullptr;
}