Using smart pointers to construct Binary Search Tree

Question

I have three main questions:

1. Am I using std::unique_ptr correctly here? Using std::move and get?

2. Is there any way for me to make my _insert and _delete functions iterative? I'd like for it to be something similar to my search function.

3. Do I need a destructor? Or since I am using automatic memory management, will all my pointers be freed when the BinarySearchTree object goes out of scope?

Thank you!

#include <iostream>
#include <memory>
#include <vector>
#include <string>
#include <stdexcept>

template <typename T> struct Node {
    T value;
    std::unique_ptr<Node> left;
    std::unique_ptr<Node> right;
    explicit Node(const T &val){value=val; left=nullptr; right=nullptr;}
} ;

template <typename T> class BinarySearchTree{
public:
    BinarySearchTree(){root = nullptr;};
    explicit BinarySearchTree(const T &value){
        root = std::make_unique<Node<T>>(value);
    }
    explicit BinarySearchTree(const std::vector<T> &array){
        for(auto &it: array) insert(it);
    }
    // Do I need a destructor?

    void insert(const T& value){
        _insert(root, value);
    }

    bool search(const T& value){
        auto curr = root.get();
        while(curr != nullptr){
           if(value == curr->value)
               return true;
           else if(value <= curr->value)
               curr = curr->left.get();
           else
               curr = curr->right.get();
        }
        return false;
    }

    void del(const T& value){
        _delete(root, value);
    }

    T min() {
        auto curr = root.get();
        while(curr->left){
            curr = curr->left.get();
        }
        return curr->value;
    }

    T max() {
        auto curr = root.get();
        while(curr->right){
            curr = curr->right.get();
        }
        return curr->value;
    }

private:
    std::unique_ptr<Node<T>> root;

    // Is there anyway to make this iterative?
    void _insert(std::unique_ptr<Node<T>> &curr, int searchVal){
        if(!curr)
            curr = std::make_unique<Node<T>> (searchVal);
        else if(searchVal <= curr->value)
            _insert(curr->left, searchVal);
        else
            _insert(curr->right, searchVal);
    }

    void _delete(std::unique_ptr<Node<T>> &curr, int deleteVal){
        // Throw error if key is not in the tree
        if(!curr){
            std::string errorVal = std::to_string(deleteVal);
            throw std::invalid_argument("Cannot find value: " + errorVal);
        }

        // Replace node if we found the key
        else if(curr->value == deleteVal)
            _deleteNode(curr);

        // Iterate down to correct key otherwise
        else if(deleteVal <= curr->value)
            _delete(curr->left, deleteVal);
        else
            _delete(curr->right, deleteVal);
    }

    void _deleteNode(std::unique_ptr<Node<T>> &toDelete){
        // Simple if it's a leaf or has only one child
        if(!toDelete->left)
            toDelete = std::move(toDelete->right);
        else if(!toDelete->right)
            toDelete = std::move(toDelete->left);
        // Replacement algorithm using inorder successor
        else{
           toDelete->value = _findSuccessor(toDelete->right);
        }
    }

    T _findSuccessor(std::unique_ptr<Node<T>> &curr){
        if(curr->left)
            return _findSuccessor(curr->left);
        else{
            T rv = curr->value;
            curr = std::move(curr->right);
            return rv;
        }
    }

} ;

int main(int argc, char** argv){
    std::vector<int> example {23,2,11,2,5,-5,6,34,8,9,42,0};
    BinarySearchTree<int> bst (example);

    std::cout << "INPUT: ";
    for(auto &it: example) std::cout << it << " ";

    std::string search47 = bst.search(47) ? " found" : " not found";
    std::string search42 = bst.search(42) ? " found" : " not found";

    std::cout << "\nSEARCHING... " << 47 << search47;
    std::cout << "\nSEARCHING... " << 42 << search42;

    std::cout << "\nMIN: " << bst.min();
    std::cout << "\nMAX: " << bst.max() << std::endl;

    std::cout << "\nDeleting minimum";
    bst.del(bst.min());
    std::cout << "\nNEW MIN: " << bst.min();

    std::cout << "\nDeleting maximum";
    bst.del(bst.max());
    std::cout << "\nNEW MAX: " << bst.max();

    return 0;
}

Answer 1

Answers to your questions

1. Am I using std::unique_ptr correctly here? Using std::move and get?

Yes, you are using those correctly.

2. Is there any way for me to make my _insert and _delete functions iterative? I'd like for it to be something similar to my search function.

Sure. An iterative solution would indeed look like your search function. However, the trick is that instead of having curr be a pointer to a Node<T>, you want curr to be a pointer to a std::unique_ptr<Node<T>>. So change curr from being a reference to being a pointer, and then you can write something like:

void _insert(std::unique_ptr<Node<T>> *curr, int searchVal){
    while (*curr) {
        if (searchVal <= (*curr)->value)
            curr = &(*curr)->left;
        else
            curr = &(*curr)->right;
    }

    *curr = std::make_unique<Node<T>>(searchVal);
}

Do I need a destructor? Or since I am using automatic memory management, will all my pointers be freed when the BinarySearchTree object goes out of scope?

Memory will automatically be freed correctly if you don't write your own destructor. However, you have to be aware that when a node is destructed, it first needs to destruct its two children, and this goes on recursively until a node doesn't have any more children. If your tree is perfectly balanced, that means O(log N) stack space is used, where N is the number of elements in the tree. But if your tree is maximally unbalanced, it will take O(N) stack space. You can avoid this by destructing one node at a time in a loop, until all the nodes are destroyed:

~BinarySearchTree() {
    while (root) {
        deleteOneNode(&root);
    }
};

However now the problem is how to delete a single node without using recursion. You can cannot delete a node with two children, since this will cause recursion. So a possible implementation is:

void deleteOneNode(std::unique_ptr<Node> *root) {
    // iterate down until we find a node with less than two children
    while ((*root)->left && (*root)->right) {
        root = root->left; // arbitrary choice
    }
    
    if ((*root)->left)
        (*root) = std::move((*root)->left);
    else if ((*root)->right)
        (*root) = std::move((*root)->right);
    else
        (*root)->reset(nullptr);
}

The drawback is that this might take O(N²) time for some trees (for the above example, one where ever left child has two children of its own, but every right child is a leaf node).

Move struct Node inside class BinarySearchTree

A Node is just an implementation detail of your BinarySearchTree, so declare the former inside the latter, like so:

template <typename T> class BinarySearchTree {
    struct Node {
        T value;
        ...;
    };

public:
    ...
};

A nice advantage is that you no longer have to write Node<T>, but can just write Node. It also no longer pollutes the global namespace with a Node, which is important if you want to use other classes that have their own Node types.

There's no need to initialize a std::unique_ptr

The default constructor of std::unique_ptr will already set the pointer to nulltpr, you don't have to do this yourself.

Prefer using member initialization lists

When initializing a member value in the constructor, use member initialization lists if possible. For example:

class Node {
    T value;
    ...
    explicit Node(const T &val): value(val) {}
};

Add a constructor that takes a pair of iterators

You have a constructor that takes a std::vector<T>, but what if I want to initialize the binary tree using data from a std::list or another STL container? You can easily make this possible by doing the same thing many STL containers do: have a constructor that takes a pair of iterators, like so:

template <class InputIt>
BinarySearchTree(InputIt first, InputIt last) {
    while (first != last) {
        insert(*first++);
    }
}

Consider adding iterators to your binary tree

It's quite common to want to iterate over all the elements of a container. If you add an iterator type, and provide begin() and end() member functions that return iterators, you can iterate over your BinarySearchTree just like other STL containers. To do it properly, you want to add other functions such as empty(), size(), cbegin()/cend(), rbegin()/rend() and so on. If you can make it work like any other STL container, that would be very nice.

Avoid starting names with underscores

There are rules governing the allowed use of underscores in C++ identifiers. Unless you want to learn all the rules by head, I would advise you to just follow these two rules:

1. Never start a name with an underscore.
2. Never use two consecutive underscores in a name.

In your code, there is no need to have separate names for the public and private functions that peform insertion and deletion. They can be distinguished by the number of arguments. So:

public:
    void delete(const T& value) {
        delete(&root, value);
    }

private:
    void delete(std::unique_ptr<Node> *curr, const T& value) {
        ...
    }

Don't cast values to int

Your public functions correctly use T for the type of values, but your private functions cast the values to int. That is quite bad! What if I want to store floating point values in your tree? If I insert {1.1, 1.2, 1.3} then internally it is converted to {1, 1, 1}. That doesn't sound very useful! Use T everywhere you handle a value.

But that also brings me to:

Allow a custom comparison function to be used

It is quite possible to have value types that themselves don't allow comparison using == and <, or that just don't provide the order in which you want them sorted in the search tree. You will notice that ordered containers like std::map allow you to specify a custom comparison function. You can easily add that to your class as well:

template <typename T, class Compare = std::less<T>>
class BinarySearchTree {
    Compare comp;
    ...
public:
    BinarySearchTree(const Compare &comp = Compare()): comp(comp), ...;
    ...
    bool search(const T& value) {
        ...
        while (...) {
           if (comp(value, curr->value)
               curr = curr->left.get();
           else if (comp(curr->value, value))
               curr = curr->right.get();
           else
               return true;
        }
    }
};