BST C++ STL implementation, visiting algorithms

Question

I am currently learning C++, and as an exercise I tried to implement a BST in a C++11. I am not sure at all if what I have done could be considered a good example of c++ programming, thus I would love to know from you if you believe my code could be improved in terms of functionalities, efficiency, or just programming style.

In particular, these are my doubts:

1. Is the use I made of unique_ptr a good idea in this situation? (It should be because of RAII, from what I got.)
2. Is the use of nested class a good idea in this situation, or even in general? In this case I think that maybe it could not be a problem because all its members are public but the class itself is encapsulated within the BinarySearchTree, so the inner class is not visible from outside the BinarySearchTreeclass.
3. I am not really sure about the checkBST function. Could it be better?

I had a look at others implementations that I was able to find on the web, in order to correct my first (and I must admit too much C-like first attempt).

template<class T> class BinarySearchTree {
private:
    // nested class for the node of the tree
    class TreeNode {
    public:
        std::unique_ptr<TreeNode> left;
        std::unique_ptr<TreeNode> right;
        T value;
        TreeNode(T val) {
            value = val;
        }
    };
    // private attributes / methods of BST class
    std::unique_ptr<TreeNode> root;   // root of the BST
    int V;                            // number of nodes
    void private_recursive_inorderVisit(TreeNode *node) {
        if(node == nullptr)
            return;

        private_inorderVisit(node->left.get());
        std::cout << node->value << std::endl;
        private_inorderVisit(node->right.get());
    }

    void private_iterative_inorderVisit(TreeNode *node) {
        TreeNode *currNode = node;
        std::stack<TreeNode*> s;
        while(s.size() > 0 || currNode != nullptr) {
            if(currNode != nullptr) {
                s.push(currNode);
                currNode = currNode->left.get();
            } else {
                currNode = s.top();
                s.pop();
                std::cout << currNode->value << ", ";
                currNode = currNode->right.get();
            }
        }
        std::cout << std::endl;
    }

public:

    BinarySearchTree(const T& RootValue) {
        std::unique_ptr<TreeNode> node(new TreeNode(RootValue));
        root = std::move(node);
        V = 1;
    }

    void insert(const T& newValue) {
        TreeNode* currentNode, *fatherNode;
        currentNode = root.get();
        fatherNode  = nullptr;
        std::unique_ptr<TreeNode> newNode(new TreeNode(newValue));

        while(currentNode != nullptr) {
            fatherNode = currentNode;

            if(newValue < currentNode->value) {
                // insert left
                currentNode = currentNode->left.get();
            } else {
                // inser right
                currentNode = currentNode->right.get();
            }
        }
        if (fatherNode->value > newValue) {
            fatherNode->left = std::move(newNode);
        } else {
            fatherNode->right = std::move(newNode);
        }

        V++;
    }

    void inorderVisit() {
        //private_recursive_inorderVisit(root.get()); // recursive method
        private_iterative_inorderVisit(root.get());
    }

    bool checkBST() {
        TreeNode *currNode = root.get(), *prevNode = root.get();
        std::stack<TreeNode*> s;
        T minVal;
        bool minFound = false;

        while(s.size() > 0 || currNode != nullptr) {
            if(currNode != nullptr) {
                s.push(currNode);
                currNode = currNode->left.get();
                if(currNode == nullptr && !minFound) { // left extreme node. Supposed to be the minimum
                    minVal = s.top()->value; // the parent of the null one is the minimum
                    minFound = true;
                }
            } else {
                // root = predecessor
                prevNode = s.top();
                s.pop();
                currNode = prevNode->right.get();
                if(prevNode->value < minVal || currNode != nullptr && currNode->value < minVal)
                    return false;
            }
        }
        return true;
    }


    int size() {
        return V;
    }

};




int main(int argc, const char * argv[]) {
    BinarySearchTree<int> BST(50);
    BST.insert(15);
    BST.insert(20);
    BST.insert(70);
    BST.insert(3);
    BST.inorderVisit();
    std::cout << "BST checked. Result is " << ((BST.checkBST() == true) ? "positive" : "negative") << std::endl;
    return 0;
}

Answer 1

I see a number of things which may help you improve your code:

Use all of the required #includes

This code requires three #includes which are missing from the code and are required in order to compile. They are:

#include <memory>
#include <stack>
#include <iostream>

Use std::make_unique

The code currently has this constructor:

BinarySearchTree(const T& RootValue) {
    std::unique_ptr<TreeNode> node(new TreeNode(RootValue));
    root = std::move(node);
    V = 1;
}

First, use the more modern initializer style for the constructor, and second, use make_unique. A revised form would look like this:

BinarySearchTree(const T& RootValue) :
    root{std::make_unique<TreeNode>(RootValue)},
    V{1}
{}

Don't allow duplicate entries

A binary search tree typically does not allow duplicate keys, but this implementation does not prevent us from adding duplicate values. To maintain the uniqueness of keys, the code should refuse to allow adding a duplicate.

Prefer smart pointers to raw pointers

Many places in the code use raw pointers rather than the smart pointers already defined within the program. As an example, consider this rewrite of iterative_inorderVisit:

void iterative_inorderVisit(const std::unique_ptr<TreeNode> *node) const {
    std::stack<const std::unique_ptr<TreeNode> *> s;
    while(s.size() > 0 || *node) {
        if(*node) {
            s.push(node);
            node = &(*node)->left;
        } else {
            node = s.top();
            s.pop();
            std::cout << (*node)->value << ", ";
            node = &(*node)->left;
        }
    }
    std::cout << std::endl;
}

Note that std::unique_ptr<T>::operator bool() const is defined as returning true if there is an underlying object or false if get() would have returned nullptr. This is used above to simplify the code. Also, the passed parameter node is used within the function -- there is no need to declare and initialize another copy.

Consider generalizing usage

The iterative_inorderVisit() function mentioned above would be more useful if it took a reference to a unary predicate. That is, instead of hardwiring the printing routine into the function, why not let the user decide what to do for each member? One could code that like this:

void iterative_inorderVisit(const std::unique_ptr<TreeNode> *node, 
    void (*unaryop)(const T&)) const 
{
    std::stack<const std::unique_ptr<TreeNode> *> s;
    while(s.size() > 0 || *node) {
        if(*node) {
            s.push(node);
            node = &(*node)->left;
        } else {
            node = s.top();
            s.pop();
            unaryop((*node)->value);
            node = &(*node)->left;
        }
    }
}

Now the public inorderVisit looks like this:

void inorderVisit(void (*unaryop)(const T&)) const {
    iterative_inorderVisit(&root, unaryop);
}

And it is called from main like this (in this case with a lambda):

BST.inorderVisit([](const std::string &s){ std::cout << s << ", "; });

Note that in this particular example, I've chosen to have a BinarySearchTree<std::string> instance instead of filling the tree with ints.

Separate member functions into logical parts

The insert function actually does two things. First, it looks through the tree for the passed key, and then it adds the node. It would probably make more sense to separate those into separate functions. Here is a suggestion for how one might implement find:

std::unique_ptr<TreeNode> &find(const T& val) {
    std::unique_ptr<TreeNode> *it = &root;
    bool done = false;
    while (!done) {
        if (val < (*it)->value) {
            if ((*it)->left) {
                it = &(*it)->left;
            } else {
                done = true;
            }
        } else if ((*it)->value < val) {
            if ((*it)->right) {
                it = &(*it)->right;
            } else {
                done = true;
            }
        } else {
            done = true;
        }
    }
    return *it;
}

This find returns either a matching TreeNode (that is, an existing node which contains the searched-for val) or the TreeNode that is the last actual node searched before the search failed. The next thing needed is a function to insert a value at a particular place in the tree:

bool insertAt(const T& newValue, std::unique_ptr<TreeNode> *here) {
    if (newValue < (*here)->value) {
        auto fresh = std::make_unique<TreeNode>(newValue);
        (*here)->left.swap(fresh);
        ++V;
    } else if ((*here)->value < newValue) {
        auto fresh = std::make_unique<TreeNode>(newValue);
        (*here)->right.swap(fresh);
        ++V;
    } else {
        return false;
    }
    return true;
}

This uses a single pointer rather than two and also only uses the < operator. This means that only that comparison operator needs to be defined for the T type. Additionally, it returns a boolean value. Given those, it is very easy to construct an insert:

bool insert(const T& newValue) {
    std::unique_ptr<TreeNode> *curr = &find(newValue);
    return insertAt(newValue, curr);
}

Use const where practical

The size function does not alter the underlying object and so should be declared const:

int size() const {
    return V;
}

Similarly, checkBST could also be const.

Try to improve naming

The size variable V is an odd and unintuitive name. Similarly, checkBST is a member function, so the BST part of that name is implicit. Instead, it could be check or maybe, verifySanity. As others have mentioned, the private_ prefix for some of your member functions is not very useful either.

Omit return 0

When a C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no reason to put return 0; explicitly at the end of main. some line with text

Answer 2

Okay some minor things here:

As I mentioned in a comment:

Naming

Why did you give your private methods the prefix private_ ? Looks code noise to me. Also these methods use cout. You should consider using an ostream-parameter (that may, or may not be defaulted to cout) instead. This way you could let the caller of the method decide whether he wants the output in a console, or a file, or sent to the international space station.

One of your methods is called inorderVisit. Consider calling it visitInOrder as method names should generally start with a verb.

Pointers

Next thing:

std::unique_ptr<TreeNode> node(new TreeNode(RootValue));

This line of code obviously works, but generally it is recommended to use make_unique instead:

std::unique_ptr<TreeNode> node = std::make_unique<TreeNode>(RootValue);

Also you are mixing unique_ptr with raw pointers. Consider using weak_ptr or shared_ptr where necessary.

Nested class

I rarely ever use nested classes, but your case here seems like it's worth an exception. This inner class is only used inside the outer class and has no sense whatsoever outside of the class. So making it an inner class seems like the way to go.

Answer 3

First of all, don't mix raw pointers with smart ones.

Also, it's a good idea to use size_t isntead of int for size, because it'll be more consistent with STL. What's more, you can implement some iterator-semantics, it'll benefit your check function too.

Finally, insert-function needs some move semantics too.