BST

BST.cpp

#ifndef BST_CPP
#define BST_CPP

#include "BST.hpp"

template <class T>
void BST<T>::addElement(const T& value)
{
    addElement(value, root);
}

template <class T>
void BST<T>::addElement(const T& value, std::shared_ptr<Node> &currentNode )
{
    if( !currentNode ){
        currentNode = std::make_shared<Node>( value );
    } else {
        auto currentNodePtr = currentNode;
        while( true ){
            if( value <= currentNodePtr->getKey() ){
                if( currentNodePtr->getLeft() ){
                    currentNodePtr = currentNodePtr->getLeft();
                } else {
                    currentNodePtr->setLeft( std::make_shared<Node>( value ) );
                    currentNodePtr->getLeft()->setParent( currentNodePtr ); return;
                }
            } else {
                if( currentNodePtr->getRight() ){
                    currentNodePtr = currentNodePtr->getRight();
                } else {
                    currentNodePtr->setRight( std::make_shared<Node>( value ) );
                    currentNodePtr->getRight()->setParent( currentNodePtr ); return;
                }
            }
        }
    }
}

template <class T>
void BST<T>::traverseBST(const std::shared_ptr<Node> &currentR, std::ostream& out)
{
    if (currentR == nullptr)
        return;
    traverseBST(currentR->getLeft(), out);
    out << currentR->getKey() << ' ';
    traverseBST(currentR->getRight(), out);
}

template <class T>
std::shared_ptr<pNode<T>> BST<T>::findElement(const T& value, const std::shared_ptr<Node> & currentR)
{
    if (currentR == nullptr)
        return currentR;
    if (currentR->getKey() == value)
        return currentR;
    else if (currentR->getKey() < value)
        return findElement(value, currentR->getRight()); //return currentR=keyNode
    else
        return findElement(value, currentR->getLeft());
}

template <class T>
void BST<T>::removeElement(const T& value)
{
    auto keyNode = findElement(value, this->root); //find the node 
    removeElement(value, keyNode);
}

//this function is only called when there is a parent for sure
template <class T>
std::shared_ptr<pNode<T>> BST<T>::findParent(const T& value,
    const std::shared_ptr<Node> & keyR, const std::shared_ptr<Node> & parentR)
{
    if (parentR == nullptr)
        return parentR;
    if (parentR->getLeft() == keyR || parentR->getRight() == keyR)
        return parentR;
    else if (parentR->getKey() < keyR->getKey())
        return findParent(value, keyR, parentR->getRight());
    else
        return findParent(value, keyR, parentR->getLeft());
}

template <class T>
void BST<T>::removeElement(const T& value, std::shared_ptr<Node> &currentR)
{
    auto linking = [](std::shared_ptr<Node>& parentP, const std::shared_ptr<Node>& newNext,
        const T& key)
    {   (key > parentP->getKey()) ? parentP->setRight(newNext) : parentP->setLeft(newNext); };

    if (!currentR)
    {
        std::cerr << "No such node\n";
        return;
    }
    else if (currentR->getLeft() == nullptr && currentR->getRight() == nullptr) //if leaf node
    {
        auto parent = findParent(value, currentR, this->root);
        if (parent == nullptr) root = nullptr;
        else linking(parent, nullptr, currentR->getKey());
        currentR.reset();
    }
    else if (currentR->getLeft() == nullptr) //if it has only right child
    {
        if (currentR == this->root)
        {
            this->root = currentR->getRight();
            currentR.reset();
            return;
        }
        auto parent = findParent(value, currentR, this->root); //find the parent of this node
        linking(parent, currentR->getRight(), currentR->getKey());
        currentR.reset();
    }
    else if (currentR->getRight() == nullptr) //if it has only left child
    {
        if (currentR == this->root)
        {
            this->root = currentR->getLeft();
            currentR.reset();
            return;
        }
        auto parent = findParent(value, currentR, this->root); 
        linking(parent, currentR->getLeft(), currentR->getKey());
        currentR.reset();
    }
    else //most complicated case
    {
        auto max = findMax(currentR->getLeft()); //find max in the left subtree
        currentR->setKey(max->getKey());
        removeElement(max->getKey(), max);
    }
}

template<class T>
std::shared_ptr<pNode<T>> BST<T>::findMax(std::shared_ptr<Node> root)//allow copying
{
    while (root->getRight() != nullptr)
    {
        root = root->getRight();
    }
    return root;
}

#endif

BST.hpp

#ifndef BST_H
#define BST_H

#include <memory>
#include <iostream>

template <class T>
class BST
{
private:
    class Node
    {
    public:
        Node() :Node(nullptr, nullptr, T{}) { }
        Node(const T& val, const std::shared_ptr<Node>& Left = nullptr,
            const std::shared_ptr<Node>& Right = nullptr) :pLeft{ Left }, pRight{ Right }, pParent{}, val{ val } { }
        void setLeft(const std::shared_ptr<Node>&);
        void setRight(const std::shared_ptr<Node>&);
        void setParent( std::shared_ptr<Node> parent );
        std::shared_ptr<Node> getLeft() const { return pLeft; }
        std::shared_ptr<Node> getRight() const { return pRight; }
        std::shared_ptr<Node> getParent() const { return pParent; }
        T getKey() const { return val; }
        void setKey(const T& val);
    private:
        std::shared_ptr<Node> pLeft;
        std::shared_ptr<Node> pRight;
        std::shared_ptr<Node> pParent{};
        T val;
    };

    std::shared_ptr<Node> root = nullptr;
    static void traverseBST(const std::shared_ptr<Node> &currentR, std::ostream& out);
    static std::shared_ptr<Node> findElement(const T& value, const std::shared_ptr<Node> & currentR);
    static std::shared_ptr<Node> findParent(const T& value,
        const std::shared_ptr<Node> & keyR, const std::shared_ptr<Node> & parentR);
    void addElement(const T& value, std::shared_ptr<Node> &currentR);
    void removeElement(const T& value, std::shared_ptr<Node> &currentR);

public:
    template <class U>
    friend std::ostream& operator<< (std::ostream&, const BST<U>&);
    std::shared_ptr<Node> findMax(std::shared_ptr<Node> root);
    void addElement(const T& value);
    void removeElement(const T& value);
};

template <class T>
using pNode = typename BST<T>::Node;

template <class T>
inline void BST<T>::Node::setLeft(const std::shared_ptr<Node> &pLeft)
{
    this->pLeft = pLeft;
}

template <class T>
inline void BST<T>::Node::setRight(const std::shared_ptr<Node> &pRight)
{
    this->pRight = pRight;
}

template <class T>
inline void BST<T>::Node::setParent( std::shared_ptr<Node> parent )
{
    pParent = parent;
}

template <class T>
inline void BST<T>::Node::setKey(const T& val)
{
    this->val = val;
}


template <class T>
inline std::ostream& operator<< (std::ostream& out, const BST<T>& tree)
{
    tree.traverseBST(tree.root, out);
    out << std::endl;
    return out;
}

#include "BST.cpp"

#endif