Implementing a binary search tree using std::unique_ptr

Question

I have implemented a binary search tree with 2 operations to begin with. I have tried to implement it using the best practices I could think of. Overall, I am happy with the implementation. But, I want someone else's opinion about what they think about the design or any bad practice I have used.

I wanted to get rid of getLeftRef() and getRightRef() functions in Node class but they are being used in insert_ and delete_ function as parameters for the recursive call. Because in the insert_ and delete_ function we are reseating the unique_ptr, I passed it by reference and according to isocpp guidelines, it is ok to pass by unique_ptr reference if it is being used to reseat the unique_ptr. It would be great to have someone's review of this bit.

P.S. I am using C++11 so I cannot use make_unique instead of using new to allocate unique_ptr.

//
//  BST.hpp
//  PracticeC++
//

#ifndef BST_hpp
#define BST_hpp

#include <memory>

// Binary Search Tree class
class BST
{
private:
    // Binary Search Tree node
    class Node
    {
    public:
        Node(int val, Node* p) : data(val), parent(p), left(nullptr), right(nullptr) {}

        bool isLeftChild() { return parent->left.get() == this; }
        bool isRightChild() { return parent->right.get() == this; }
        Node* getLeft() { return left.get(); }
        Node* getRight() { return right.get(); }
        Node* getParent() { return parent; }
        std::unique_ptr<Node>& getLeftRef() { return left; }
        std::unique_ptr<Node>& getRightRef() { return right; }
        int getData() { return data; }

        std::unique_ptr<Node> extract()
        { return isLeftChild() ? std::move(parent->left) : std::move(parent->right); }

        std::unique_ptr<Node> extractLeft() { return std::move(left); }

        std::unique_ptr<Node> extractRight() { return std::move(right); }

        void setLeft(std::unique_ptr<Node> n)
        {
            if (!n)
                return;

            n->Reparent(this);
            left = std::move(n);
        }

        void setRight(std::unique_ptr<Node> n)
        {
            if (!n)
                return;

            n->Reparent(this);
            right = std::move(n);
        }

        void resetParent() { parent = nullptr; }
        void setData(int val) { data = val; }

    private:
        // member variables
        int data;
        std::unique_ptr<Node> left;
        std::unique_ptr<Node> right;
        Node* parent;

        void Reparent(Node* newParent) { parent = newParent; }
    };

    void insert_(std::unique_ptr<Node>& root, int val, Node* parent);
    bool remove_(std::unique_ptr<Node>& root, int val, Node* parent);
    std::unique_ptr<Node> extractInOrderPredOrSucc(Node* node, bool isPred);

    Node* find(Node* n, int val);
    Node* findInOrderPredecessor(Node* node);
    Node* findInOrderSuccessor(Node* node);

    // Member variables
    std::unique_ptr<Node> root;
public:

    void insert(int val) { insert_(root, val, nullptr); }
    bool remove(int val) { return remove_(root, val, nullptr); }
};


#endif /* BST_hpp */

//
//  BST.cpp
//  PracticeC++
//
//

#include "BST.hpp"

BST::Node* BST::findInOrderPredecessor(BST::Node* node)
{
    if (!node || !node->getLeft())
        return nullptr;

    node = node->getLeft();

    while (node->getRight())
        node = node->getRight();

    return node;
}

BST::Node* BST::findInOrderSuccessor(BST::Node* node)
{
    if (!node)
        return nullptr;
    else if (!node->getRight())
        return node->getParent();

    node = node->getLeft();

    while (node->getRight())
        node = node->getRight();

    return node;
}

std::unique_ptr<BST::Node> BST::extractInOrderPredOrSucc(BST::Node* node, bool isPred)
{
    if (isPred)
    {
        Node* n = findInOrderPredecessor(node);
        if (!n)
            return nullptr;
        auto subtree = n->extract();
        subtree->getParent()->setRight(subtree->extractLeft());
        subtree->resetParent();
        return subtree;
    }
    else
    {
        Node* n = findInOrderSuccessor(node);
        if (!n)
            return nullptr;
        auto subtree = n->extract();
        subtree->getParent()->setLeft(subtree->extractRight());
        subtree->resetParent();
        return subtree;
    }
}

void BST::insert_(std::unique_ptr<Node>& node, int val, Node* parent)
{
    if (!node)
    {
        node = std::unique_ptr<Node>(new Node(val, parent));
        return;
    }

    return (val <= node->getData()
            ? insert_(node->getLeftRef(), val, node.get())
            : insert_(node->getRightRef(), val, node.get()));
}

bool BST::remove_(std::unique_ptr<Node>& node, int val, Node* parent)
{
    if (!node)
        return false;

    if (val == node->getData())
    {
        if (!node->getLeft())
        {
            if (!node->getRight())
                node.reset();
            else
                node->setRight(node->extractRight());
        }
        else
        {
            if (!node->getRight())
                node->setLeft(node->extractLeft());
            else
            {
                // Both children exist, so replace with either in-order pred or succ
                auto predNode = extractInOrderPredOrSucc(node.get(), true);

                predNode->setLeft(node->extractLeft());
                predNode->setRight(node->extractRight());

                node->isLeftChild()
                ? node->getParent()->setLeft(std::move(predNode))
                : node->getParent()->setRight(std::move(predNode));
            }
        }

        return true;
    }

    return (val < node->getData()
            ? remove_(node->getLeftRef(), val, node.get())
            : remove_(node->getRightRef(), val, node.get()));
}

Answer 1

Observation

I normally don't see a parent pointer in a binary tree.
Because you have to keep and maintain this extra pointer your code is a lot more complicated then it needs to be.

---

The Node object is part of BST so you don't need need an interface to protect you from changes. Any changes in the BST or node are going to result in changes in the other.

As a result I would simplify the Node to be a simple structure and get rid of that confusing mess of accessor functions.

---

Personally I don't use smart pointers to build containers. The container is its own manager of memory abstracting that out is redundant. Though others would argue with me on that point and I do see their point.

---

Your code can only store int. Why did you make this limitation. A simple templatization will allow you to store any type that is comparable.

Alternative

This is to show that you made the code twice as long by simply adding the parent member to the class.

template<typename T>
class BST
{
    struct Node
    {
        Node*     left;
        Node*     right;
        T         value;
    };
    Node* root = nullptr;

    // This function assumes node is not null.
    // So check before you call.
    Node* findLeftMostNode(Node* node) {
        return node->left == nullptr ? node: findLeftMostNode(node->left);
    }

    Node* insertNode(Node* node, T consT& val) {
        if (node == nullptr) {
            return new Node{nullptr, nullptr, val};
        }

        if (val < node->value) {
            node->left = insertNode(node->left, val);
        }
        else {
            node->right = insertNode(node->right, val);
        }
        return node;
    }
    Node* deleteNode(Node* node, T const& val)
    {
        if (node == nullptr) {
            return nullptr;
        }
        if (val < node->val) {
            node->left = deleteNode(node->left, val);
        }
        else if (val > node->val) {
            node->right = deleteNode(node->right, val);
        }
        else {
            // The interesting part.
            Node* old = node;           // the node to delete;

            // If both children are null.
            // Simply delete the node and return nullptr
            // as the value to be used for this point.
            if (node->left == nullptr && node->right == nullptr) {
                node = nullptr;
            }
            // If either the left or right node is null
            // then we can use the other one as the replacement for
            // for node in the tree.
            else if (node->left == nullptr) {
                node = node->right;        // the node to return as replacement
            }
            else if (node->right == nullptr) {
                node = node->left;         // the node to return as replacement
            }
            else {
                // The shit just got real.
                // We can't delete the node (as we can return two pointers)
                old = nullptr;

                // This is the complicated part.
                // Remember that both the left and right are not nullptr.
                // So the leftmost sub-node of the right tree is the smallest
                // value in the right subtree. 
                // If we move this value to here then the right sub-tree can
                // still be on the right of this node.
                Node* leftMost = findLeftMostNode(node->right);
                // Don't need to re-shape the tree simply move the value.
                node->val   = leftMost->val;

                // We have moved the value.
                // But now we have to delete the value we just moved from the
                // right sub-tree. Luckily we have a function for that.
                node->right = deleteNode(node->right, leftMost->val);
            }
            delete old;
        }
        return node;
    }

    public:
        ~BST()
        {
            Node* bottomLeft = root == nullptr ? nullptr : findLeftMostNode(root);

            while (root) {
                Node* old = root;
                root = root->left;
                bottomLeft->left = old->right;
                bottomLeft = findLeftMostNode(bottomLeft);
                delete old;
            }
        }
        // Deletet the copy operator
        BST(BST const&)           = delete;
        BST& operator(BST const&) = delete;

        // Simple interface.
        void insertNode(T const& val) {root = insertNode(root, val);}
        void deleteNode(T const& val) {root = deleteNode(root, val);}
}