Binary Search Tree C++ Implementation

Question

I've implemented a simple binary search tree for practice purposes:

#ifndef BST_H
#define BST_H
template <typename T>
class treeNode {
public:
    treeNode *left;
    treeNode *right;
    T key;
    treeNode(T key)
        : key(key)
        , left(nullptr)
        , right(nullptr) {
    }
};

template <typename T>
class BST {
public:
    BST() {
        root = nullptr;
        nodes = 0;
    }

    BST(BST const& rhs)
        : nodes(rhs.size()) {
        // not yet implemented
    }

    BST& operator = (BST rhs) {
        this->swap(rhs);
    }

    BST& operator = (BST&& rhs) {
        this->swap(rhs);
    }

    ~BST() {
        clear(root);
    }

    void swap(BST& other) {
        std::swap(root, other.root);
        std::swap(nodes, other.nodes);
    }

    void clear(treeNode<T>* node) {
        if(node) {
            if(node->left) clear(node->left);
            if(node->right) clear(node->right);
            delete node;
        }
    }

    bool isEmpty() const {
        return root == nullptr;
    }
    void inorder(treeNode<T>*);
    void traverseInorder();

    void preorder(treeNode<T>*);
    void traversePreorder();

    void postorder(treeNode<T>*);
    void traversePostorder();

    void insert(T const& );

    void remove(T const& );

    treeNode<T>* search(const T &);

    treeNode<T>* minHelper(treeNode<T>*);
    treeNode<T>* min();

    treeNode<T>* maxHelper(treeNode<T>*);
    treeNode<T>* max();

    size_t size() const;

    void sort();
    treeNode<T>* inOrderSuccessor(treeNode<T>*);
    bool isBST(treeNode<T>*) const;
    bool isBST() const;

private:
    treeNode<T> *root;
    size_t nodes;
};

// Smaller elements go left
// larger elements go right
template <class T>
void BST<T>::insert(T const& value) {
    treeNode<T> *newNode = new treeNode<T>(value);
    treeNode<T> *parent = nullptr;

    // is this a new tree?
    if(isEmpty()) {
        root = newNode;
        ++nodes;
        return;
    }
    //Note: ALL insertions are as leaf nodes
    treeNode<T>* curr = root;
    // Find the Node's parent
    while(curr) {
        parent = curr;
        curr = newNode->key > curr->key ? curr->right : curr->left;
    }

    if(newNode->key < parent->key)
        parent->left = newNode;
    else
        parent->right = newNode;

    ++nodes;
}

template <typename T>
void BST<T>::remove(T const& data) {

    if(isEmpty()) {
        throw std::runtime_error("Invalid Action!");
    }

    treeNode<T> *curr = root;
    treeNode<T> *parent;

    // root to leaf search (top-down)
    while(curr) {
        if(curr->key == data) {
            break;
        } else {
            parent = curr;
            curr = data > curr->key ? curr->right : curr->left;
        }
    }

    if(curr == nullptr) {
        cout << "key not found! " << endl;
        return;
    }


    // 3 cases :
    // 1. We're removing a leaf node
    // 2. We're removing a node with a single child
    // 3. we're removing a node with 2 children


    //We're looking at a leaf node
    if( curr->left == nullptr and curr->right == nullptr) {
        if(parent->left == curr)
            parent->left = nullptr;
        else
            parent->right = nullptr;

        delete curr;
        --nodes;
        return;
    }

    // Node with single child
    if((curr->left == nullptr and curr->right != nullptr) or (curr->left != nullptr and curr->right == nullptr)) {
        if(curr->left == nullptr and curr->right != nullptr) {
            if(parent->left == curr) {
                parent->left = curr->right;
            } else {
                parent->right = curr->right;
            }
        } else { // left child present, no right child
            if(parent->left == curr) {
                parent->left = curr->left;
            } else {
                parent->right = curr->left;
            }
        }
        delete curr;
        --nodes;
        return;
    }

    // Node with 2 children
    // replace node with smallest value in right subtree
    if (curr->left != nullptr and curr->right != nullptr) {
        treeNode<T> *curr_right = curr->right;
        if(curr_right->left == nullptr and curr_right->right == nullptr) {
            curr->key = curr_right->key;
            delete curr_right;
            curr->right = nullptr;
        } else { // right child has children
            //if the node's right child has a left child
            // Move all the way down left to locate smallest element

            if((curr->right)->left != nullptr) {
                treeNode<T>* lcurr;
                treeNode<T>* lcurr_parent;
                lcurr_parent = curr->right;
                lcurr = (curr->right)->left;
                while(lcurr->left != nullptr) {
                    lcurr_parent = lcurr;
                    lcurr = lcurr->left;
                }
                curr->key = lcurr->key;
                delete lcurr;
                lcurr_parent->left = nullptr;
            } else { // (curr->right)->right != nullptr
                treeNode<T> *tmp = curr->right;
                curr->key = tmp->key;
                curr->right = tmp->right;
                delete tmp;
            }
        }
        --nodes;
    }

}

template <typename T>
treeNode<T>* BST<T> :: search(T const& value) {
    treeNode<T> *curr = root;
    while (curr) {
        if(curr->key == value) {
            return curr;
        } else if(value < curr->key) {
            curr = curr->left;
        } else curr = curr->right;
    }
    return nullptr;
}

template <typename T>
treeNode<T>* BST <T> :: minHelper(treeNode<T>* node) {
    if(node->left == nullptr)
        return node;
    minHelper(node->left);
}

template <typename T>
treeNode<T>* BST <T> :: min() {
    return minHelper(root);
}

template <typename T>
treeNode<T>* BST <T> :: maxHelper(treeNode<T>* node) {
    if(node->right == nullptr)
        return node;
    maxHelper(node->right);
}

template <typename T>
treeNode<T>* BST <T> :: max() {
    return maxHelper(root);
}

template<typename T>
size_t BST<T>::size() const {
    return nodes;
}

template<typename T>
void BST<T>::inorder(treeNode<T>* node) {
    if(node != nullptr) {
        if(node->left) inorder(node->left);
        cout << " " << node->key << " ";
        if(node->right)
            inorder(node->right);
    }
}

template<typename T>
void BST<T>::traverseInorder() {
    inorder(root);
}

template<typename T>
void BST<T>::sort() {
    inorder(root);
}

template<typename T>
void BST<T>::preorder(treeNode<T>* node) {
    if(node != nullptr) {
        cout << " " << node->key << " ";
        if(node->left) preorder(node->left);
        if(node->right) preorder(node->right);
    }
}

template<typename T>
void BST<T>::traversePreorder() {
    preorder(root);
}

template<typename T>
void BST<T>::postorder(treeNode<T>* node) {
    if(node != nullptr) {
        if(node->left) postorder(node->left);
        if(node->right) postorder(node->right);
        cout << " " << node->key << " ";
    }
}

template<typename T>
void BST<T>::traversePostorder() {
    postorder(root);
}

template <class T>
treeNode<T>* BST<T> :: inOrderSuccessor(treeNode<T>* node) {
    if(node->right != nullptr)
        return minHelper(node->right);

    treeNode<T>* succ = nullptr;
    treeNode<T>* curr = root;
    // Start from root and search for successor down the tree
    while (curr != nullptr) {
        if (node->key < curr->key) {
            succ = curr;
            curr = curr->left;
        } else if (node->key > curr->key)
            curr = curr->right;
        else
            break;
    }
    return succ;
}

template<typename T>
bool BST<T>::isBST(treeNode<T>* node) const {
    static struct treeNode<T> *prev = nullptr;

    // traverse the tree in inorder fashion and keep track of prev node
    if (node) {
        if (!isBST(node->left))
            return false;

        // Allows only distinct valued nodes
        if (prev != nullptr and node->key <= prev->key)
            return false;

        prev = node;

        return isBST(node->right);
    }

    return true;
}

template<typename T>
bool BST<T>::isBST() const {
    return isBST(root);
}
#endif // BST_H

Obviously it's not a complete implementation. I would appreciate all criticism relevant to code, style, flow, camelCase vs underscore, and so forth.

Answer 1

Inconsistent Code Style

Choose one coding style and use it. Some tips:
PascalCasing can be used for class/type names, but especially for template parameters.
camelCasing is mostly Java-style and fits for methods and variables (especially local vars).
c_uses_underscores almost for everything except template parameters (you can see it everywhere).
Choose what you wan't, some use CMyClass and TMyTemplate (Microsoft MFC/ATL Style), but once you choose one, use it everywhere - don't mix it.

Accessibility (what is public, private or protected)

You can use struct (all public) for your test code, but if you want to become good programmer, think about what should be public, private or protected (the last is for derived classes). I would start like this:

/// Binary Search Tree (note: this is Doxygen style documentation comment)
template<class T> class bstree { // bintree, BinarySearchTree, C/TBinTree... as you choose
    struct node { // private as first things in class are private for a good reason
        node *left, *right; // you can split it to two lines and comment like following:
        T value;   ///< node value (again, Doxygen will generate documentation from this)
    }; // no need for a constructor, it is our private struct (or protected if you like)
    node *root;    ///< root node (I prefer data first in class to see what we use)
    size_t count;  ///< nodes is not a good name, count, size, number...
public: // now is the time to show what we can do

Now I will clear it of those comments:

/// Binary Search Tree
template<class T> class bstree {
    struct node {
        node *left;   ///< left node (if any)
        node *right;  ///< right node (if any)
        T value;      ///< stored value
    };
    node *root;       ///< root node
    size_t count;     ///< total number of nodes in the tree
public:
    bstree(): root(nullptr), count(0) {}

Doxygen will be able to generate nice documentation for you if you get used to those /// comments before and ///< comments after.

I think that node should be either private or protected, because you present data storage, not the nodes. You can use T or name it ValueType, but I prefer T for single template parameter - it is obvious what it is.

(note: some prefer not to use protected at all, I disagree: helpers private, interface public, usable internals as protected for further sub-classing and enhancements. Makes sense for non-virtual classes/templates as well when we want to create new container with new/different features and new data for the features - e.g. fast lookup for last searched node, or flat_set from vector. I have reworded the last sentence a bit - see comments below. In short: don't inherit publicly, use private/protected base when there is a public non-virtual destructor.)

Copy/Move and Default Constructors + operator =

You should understand lvalue and rvalue references first. If you don't know what && is good for (std::move, std::forward), stick with const T& const reference for a while. BTW: I have seen T const& pattern in your code - I prefer const T& because it shows what is const (the value, not the reference - like const T* means cannot change the value pointed to, not cannot change the pointer), but it is your style, use it if you wish.

bstree();              ///< default constructor
bstree(const bstree&); ///< copy constructor (preserve what is passed)
bstree(bstree&&);      ///< move constructor (may destroy/clear what is passed)
bstree& operator = (const bstree&); ///< copy assignment
bstree& operator = (bstree&&);      ///< move assignment
bstree& operator = (bstree);        ///< wrong! would make a copy first, then like bstree&&

edit note: The last can be used in copy-and-swap idiom as pointed out by rudus, but there was no move constructor. Another link about that topic here.

Move will destroy the right side, swapping makes no sense (edit: now I see the intent - leave the destruction on the swallowed rvalue). But beware not to call rhs.clear() because that could dispose the nodes:

/// move assignment
    bstree& operator = (bstree&& rhs) {
        if(&rhs == this)    // we better check
            return *this;   // not to dispose our nodes
        clear();            // dispose ours first
        root = rhs.root;    // 'steal' the nodes
        count = rhs.count;  // get the count
        rhs.root = nullptr; // clear the other
        rhs.count = 0;      // and count it
        return *this;       // this comes last
    }

Errors

remove: uninitialized parent - what about removing the last node?
...I am finished, unless you rewrite it and comment, what is what, what and how it should do it ;)

Have a nice day :) I hope I was not too harsh :)

---

Addendum

All those nice upvotes encouraged me, to rethink the design a bit. Here is my (incomplete) code on IdeOne.com using std::unique_ptr.

Constructors, copy and move

/// Default constructor for empty tree
    bstree(): root(), count(0) {}
//note: no need for a destructor, we use managed pointers
//  ~bstree() {}
/// Copy constructor
    bstree(const bstree& src)
    : root(src.root->copy()), count(src.count) {}
/// Move constructor
    bstree(bstree&& rhs)
    : root(std::move(rhs.root)), count(rhs.count) {
        rhs.count = 0; }
/// Move assignment
    bstree& operator = (bstree&& rhs) {
        root.swap(rhs.root);
        std::swap(count, rhs.count);
        return *this; }
/// Copy assignment
    bstree& operator = (const bstree& rhs) {
        if (this != &rhs) {// no self-copy
            root.reset(rhs.root->copy());
            count = rhs.count; }
        return *this; }

Few methods

bool contains(const T& value) {
    return root && root->find(value); }
bool insert(const T& value) {
    ptr* where = &root;
    if(root) {
        where = root->where(value);
        if(!where) return false; }
    where->reset(new node(value));
    ++count; return true;
}

Core

/// Binary Search Tree
template<class T> class bstree {
// I will make use of protected, feel free to use private only
// ... can be used to create another template
// ... or for debug purposes - printouts in such derived class
// ... but remember to never inherit publicly
// ... because it has public non-virtual destructor
//================================================================== node
protected:
    struct node;    // forward declaration
    typedef std::unique_ptr<node>
        ptr;        ///< managed pointer to node
    struct node {
        ptr left;   ///< left node (if any)
        ptr right;  ///< right node (if any)
        T value;    ///< stored value
    //------------------------------------------------ node: construction
        node() {}
        node(
          const T& value,
          node* left = nullptr,
          node* right = nullptr)
        : left(left), right(right), value(value) {}
        node(
          T&& value,
          node* left = nullptr,
          node* right = nullptr)
        : left(left), right(right), value(value) {}
    //--------------------------------------------------- node: deep copy
    /// Make a deep copy of all nodes. May be called on null as well.
        node* copy() {
            return !this ? nullptr :
              new node(value,
              left->copy(),
              right->copy());
        }
    //-------------------------------------------------- node: find value
    /// Find node with specified value. May be called on null as well.
        node* find(const T& what) {
            node* it = this;
            while(it) {
                if(what < value)
                    it = it->left.get();
                else if(value < what)
                    it = it->right.get();
                else break;
            }
            return it;
        }
    //------------------------------------------------- node: place value
    /// Find place for new node \return null if already there
        ptr* where(const T& what) {
            node* it = this;
            ptr* where;
            for(;;) {
                if(what < it->value) {
                    if(!it->left) return &it->left;
                    it = it->left.get();
                } else if(it->value < what) {
                    if(!it->right) return &it->right;
                    it = it->right.get();
                } else return nullptr;
            }
        }
    };
//================================================================== data
protected:
    ptr root;       ///< root node
    size_t count;   ///< total number of nodes
//====================================================== ctor, copy, move
public:
/// Default constructor for empty tree
    bstree(): root(), count(0) {}
//note: no need for a destructor, we use managed pointers
//  ~bstree() {}
/// Copy constructor
    bstree(const bstree& src)
    : root(src.root->copy()), count(src.count) {}
/// Move constructor
    bstree(bstree&& rhs)
    : root(std::move(rhs.root)), count(rhs.count) {
        rhs.count = 0; }
/// Move assignment
    bstree& operator = (bstree&& rhs) {
        root.swap(rhs.root);
        std::swap(count, rhs.count);
        return *this; }
/// Copy assignment
    bstree& operator = (const bstree& rhs) {
        if (this != &rhs) {// no self-copy
            root.reset(rhs.root->copy());
            count = rhs.count; }
        return *this; }
//=============================================================== methods
public:
    bool contains(const T& value) {
        return root && root->find(value); }
    bool insert(const T& value) {
        ptr* where = &root;
        if(root) {
            where = root->where(value);
            if(!where) return false; }
        where->reset(new node(value));
        ++count; return true;
    }
    bool insert(T&& value) {
        ptr* where = &root;
        if(root) {
            where = root->where(value);
            if(!where) return false; }
        where->reset(new node(value));
        ++count; return true;
    }
};

...feel free to comment if you find some bug :)

Answer 2

Keeping the BST a BST

The current implementation allows adding duplicate values. If you call ::insert(x) and then again ::insert(x) it will happily add x twice, violating the requirement of no duplicate values. If you want to keep it a BST, then you need to add some checks for equality and either throw an exception, or ignore the value.

Cleaner algorithm for isBST

I don't really like the static prev pointer in the isBST method. I think it would be more elegant to use minValue, maxValue guards instead:

bool BST<T>::isBST(treeNode<T>* node, int maxValue, int minValue) const {
    if (!node) {
        return true;
    }

    if (node->key >= maxValue || node->ket <= minValue) {
        return false;
    }

    return isBST(node->left, node->key, minValue) && isBST(node->right, maxData, node->key);
}

std::

I see you are using the namespace prefix for std::swap and std::runtime_error, but not for cout. Does this compile? I think you should use std::cout.

Inconsistent writing style

The writing style of your method signatures is not consistent:

template <typename T>
treeNode<T>* BST <T> :: max() {
    return maxHelper(root);
}

template<typename T>
size_t BST<T>::size() const {
    return nodes;
}

In the first one you put spaces in BST <T> :: but in the second you didn't. Half of your methods are one way, the other half the other. Use a consistent writing style, I recommend the second (no spaces).

Other coding style related

I recommend to use braces even with single statement ifs. It's unambiguous, and it can help avoid embarrassing bugs. Especially in inOrderSuccessor you have some else-ifs that can be confusing and error prone.

---

I think it's more common to use CamelCase for class names. So TreeNode instead of treeNode.

Personally I would find TreeNode.value more natural instead of TreeNode.key, but maybe that's just me. Actually, I just noticed that you named the parameter of ::insert(T const&) as value. So it's not just me, it's you too :-)

Answer 3

Regarding treeNode implementation.

- Use self documenting naming for template arguments.

template <typename T>; what is T? Let's use something such as ValueType. Maybe in this case is not really required but nevertheless is a good practice.

- Name your classes and structures with a capital letter.

class treeNode => class TreeNode

More like my personal preference, but is good to have your classes starting with capital letter. Standard library is an exception. If you have such a coding guideline then this is no issue at all.

Also many libraries are using the same guideline so it should be more expected to find it in various projects.

- Do not use pointers in C++

If we're using C++ we are not using pointer types unless really required and backed up by a reasonable explanation. Instead, what we do is use smart pointers or objects. So for your treeNode we would have:

private:
    std::unique_ptr<treeNode> left;
    std::unique_ptr<treeNode> right;

which leads me to the next point...

- Avoid public data members especially when those are pointers

Have your treeNode class provide access to those data members through specific methods. You can then include debug only asserts, return objects by ref and do various improvements to your code, something like:

const TreeNode& LeftChild() const 
{
    assert(_left  != NULL);
    return *_left;
}

Regarding BST implementation

(what I said above still applies here - I will not repeat'em).

- Use a self documenting name instead of BST.

BinarySearchTree is quite fine. But this is the smallest issues here.

- This class is buggy, semantically wrong, doesn't make sense and is very confusing

Here is a rough list of issues:

1. All your method expect a treeNode as parameter. Why? As a user of your class I expect to be able to call clear() without having the need to send the root object.
2. I have no idea what void traversePostorder(); does. Receives nothings, returns nothing. I don't want to read the implementation to figure it out.
3. Why are minHelper, min, maxHelper and max methods public? I have no idea what they do and why are they public. Again, I don't want to look in your implementation to figure it out.
4. Calling clear method will not reset the size to 0. So I have a tree, I call clear on it, but when I ask for its size it is not 0. This is a major bug.
5. isBST again, the naming is very confusing? Does this check that the current instance is a BST? Why wouldn't it be, since it is named BST. Please rework the naming.

Here is an API example you should be using:

<template ValueType>
class BinarySearchTree
{

public:

    ///Construct an empty binary search tree.
    BinarySearchTree();

    void Insert(const ValueType& elementToInsert);

    /// Removes the provided element, if found.
    /// return true if the element was found or false otherwise
    bool Remove(const ValueType& elementToRemove);

    /// Search for the provided element.
    bool Contains(const ValueType& elementToFind) const;

    /// Empty the tree
    void Clear();

    /// True when size() == 0
    bool IsEmpty() const;

    /// Number of elements the tree currently holds
    size_t Count() const;

    typedef const TreeNode<const ValueType&>& NodeConstRef;

    //[personal note]: 
    //  I would provide iterators based on TreeNode implementation.
    NodeConstRef Root() const;

    //Add more... as required.

}

Take note that this is just a simple example I wrote directly here. You should adapt it to fit your needs. If I were to make a binary tree implementation for generic purposes I would aim at providing an interface as close as possible to standard library (mainly providing proper iterators for your tree). This means also changing the TreeNode implementation and maybe using methods such as size(), insert etc. But mainly iterators, those are the most important part.

Then you can use stuff like std::find or std::transform and so on for working with your tree, so you no longer need to implement all that.

And finally few more words regarding your implementations...

Method implementations

- Your methods should never make use of std::cout. Never.

I will not go into details here, just look at other code reviews on C++ codes as this is a very common mistake. There are people who explained it better than I can do it.

- BST<T>::remove is simply not readable.

Too much code, too chaotic, inconsistent... For instance, why are your throwing std::runtime_error if the tree is empty but just logging to console if curr == nullptr?

Really, I don't even know what to say here, you need to tackle simpler problems before dealing with this. Basically every single line from this method has something wrong in it. Dealing with the API, the treeNode implementation and cleaning the whole design would render this method useless.

Even more, if you take my advice and use iterators, you can just call std::remove and completely delete this monstrosity.

... and more

Heavy usage of pointers, dereferencing pointers without checking, many if-else branches, breaking while loops when going through the tree, mixing recursion with iterative algorithms in the same method.

Final suggestions

Please tackle smaller problems. Something that fits in 20 lines of code or so. You could even aim to learn a bit of C before and slowly move to C++. You'll get much better code reviews if you solve problems that match your skill level.

Also, it is mandatory for you to learn standard template library. Learn to work with smart pointers, collections, iterators and algorithms provided by std.

There are so many improvements here that I could write 20 times as much as I did here and I still wouldn't cover it all. So start with smaller problems or ask review on smaller parts of your code until you get better.

Answer 4

I will focus on remove, because it is very large and seemingly complicated, hence it immediately attracts a reviewer attention.

• I don't think throwing an exception on empty tree is a good practice. In all practical applications, an empty tree is no different for a key not found situation. That said, "Invalid Action! is not very informative.

• There's no need for 3 cases. In any circumstances, you'd replace a removed node with another tree built from its left and right subtrees. Which means that a BST::combine() method is in order (trust me, it will seriously simplify the code).

• and and or give me goosebumps. Please stick to && and ||.