Binary search tree with templates

Question

I am currently attempting to become proficient in C++ and started by implementing a basic binary search tree. Most of the programming I have done is in Ada, Python and C.

I would like to be able to program efficiently in modern C++ and become familiar with current best practices. I do not have any major questions or concerns beyond the fact that I am not entirely comfortable with the usage of smart pointers. I was hoping some people would simply be willing to critique this code and explain any major problems they may see.

I am considering adding an iterator interface but am unsure if I will move forward with that right now. The tree currently works properly for my test cases.

Header File

#ifndef BST_H
#define BST_H
#include <memory>
template <class BST>
class BinarySearchTree
{
private:
/*----------------------------------------------------------------------/
/ Type Declarations /
/*---------------------------------------------------------------------*/
struct node_t;
typedef std::unique_ptr<node_t> node_p;
struct node_t
//Represents one node of tree data
{
 BST data;
 node_p left;
 node_p right;
 //node_t constructor
 node_t(const BST &item):data(item), left(nullptr), right(nullptr){}
};
//Type representing connections of a node.
enum limb_t {Right, Left};
/*----------------------------------------------------------------------/
/ Class Variables /
/*---------------------------------------------------------------------*/
node_p root;
int tree_size;
/*----------------------------------------------------------------------/
/ Private functions /
/*---------------------------------------------------------------------*/
bool _search(const BST &item, node_t * &parent, node_t * &current) const;
/*Function searches the tree for the value of item
 Sets the parent and current node to the the location of the item if found.
 Returns boolean value for the result of the search*/
void remove_with_children(node_t * &node);
/*Replaces the target node's data with the minimum data found in the right subtree
 Deletes the node with the minimum data is then deleted.*/
node_t * find_min_r_sub(const node_t &node) const;
/*Function locates the minumum data in the given nodes right subtree
 Returns a node pointer to the item containing the minimum data*/
void remove_with_child(node_t * &parent, node_t * &current);
/*Replaces the node to be deleted with the existing node on the parent nodes left or right limb
 Node is deleted after the the move is made*/
void remove_leaf(node_t * &parent, node_t * &current);
/*Function deletes the target node.*/
bool has_child(const node_t &node, const limb_t limb) const;
/*Reports True if child is found on given node on given limb. False if not*/
bool is_empty(void) const;
/*Checks if tree is empty
 Returns boolean value for if tree is empty or not
*/
/*----------------------------------------------------------------------/
/ Private Print Functions /
/*---------------------------------------------------------------------*/
void _postorder(const node_p &node) const;
/*Recursively prints the BST in postorder format.*/
void _preorder(const node_p &node) const;
/*Recursively prints the BST in preorder format.*/
void _inorder(const node_p &node) const;
/*Recursively prints the BST in inorder format.*/
public:
/*----------------------------------------------------------------------/
/ Constructor and Destructor /
/*---------------------------------------------------------------------*/
BinarySearchTree(void);
/*Creates tree object,
 Sets root to a nullptr and tree_size to 0.*/
~BinarySearchTree(void);
/*Destroys the tree object
 Resets the root node and sets tree_size to 0.*/
/*----------------------------------------------------------------------/
/ Public Functions /
/*---------------------------------------------------------------------*/
bool insert(const BST &item);
/*Inserts item into the tree.
 Returns true if insertions was successful.
 Does not allow duplicate items to be inserted.*/
bool remove(const BST &item);
/*Removes given item from the tree.
 Returns false if item not in the tree,
 true if removal was successful.*/
bool search(const BST &item) const;
/*Calls private serch function and searches for the given item
 Results are returned as a boolean falue.*/
/*----------------------------------------------------------------------/
/ Public Print Functions /
/*---------------------------------------------------------------------*/
void inorder(void) const;
/*Public function for printing tree in inorder format.*/
void preorder(void) const;
/*Public function for printing tree in preorder format.*/
void postorder(void) const;
/*Public function for printing tree in postorder format.*/
};
#endif

Class Body

#include "BinarySearchTree.h"
#include <iostream>
template <class BST>
BinarySearchTree<BST>::BinarySearchTree(void)
{ 
 root = nullptr;
 tree_size = 0;
}
template <class BST>
BinarySearchTree<BST>::~BinarySearchTree(void)
{
 root.reset();
 tree_size = 0;
}
template <class BST>
bool BinarySearchTree<BST>::insert(const BST &item)
{
 node_p new_leaf(new node_t(item));
 if(is_empty())
 {
 root = std::move(new_leaf);
 }
 else
 {
 node_t * current = root.get();
 node_t * parent = nullptr;
 while(current)
 /*-Node searches for null position to insert new node if item is not in tree.
 -Each iteration traverses one node and sets next node.*/
 {
 parent = current;
 if(current->data > item)
 {
 current = current->left.get();
 }
 else if (current->data < item)
 {
 current = current->right.get();
 } 
 else
 { //The case that the item is found in the tree.
 return false;
 }
 }
 if(parent->data > item) //Insert item.
 {
 parent->left = std::move(new_leaf);
 }
 else
 {
 parent->right = std::move(new_leaf);
 }
 }
 //Increment tree size.
 tree_size++;
 return true;
}
template <class BST>
bool BinarySearchTree<BST>::remove(const BST &item)
{
 if(is_empty())
 {
 return false;
 }
 node_t * parent;
 node_t * current;
 if(_search(item, parent, current))
 {
 if(has_child(*current, Left) && has_child(*current, Right))
 { //node has a left and right child.
 remove_with_children(current);
 }
 else if(has_child(*current, Left) != has_child(*current, Right))
 { //node has a single child.
 remove_with_child(parent, current);
 }
 else
 { //node has no children.
 remove_leaf(parent, current);
 }
 //Decrement tree size.
 tree_size--;
 }
 else
 { //node was not found.
 return false;
 }
 return true;
}
template <class BST>
bool BinarySearchTree<BST>::_search(const BST &item, node_t * &parent, node_t * &current) const
{
 parent = nullptr;
 current = root.get();
 while(current)
 /*-Loop searches for item in the tree.
 -Each iteration traverses and checks one node.*/
 {
 if(item == (current)->data)
 {
 return true;
 }
 else
 {
 parent = current;
 if(item > current->data)
 {
 current = current->right.get();
 }
 else
 {
 current = current->left.get();
 }
 }
 }
 return false;
}
template <class BST>
void BinarySearchTree<BST>::remove_with_children(node_t * &node)
{
 node_t * min_parent;
 min_parent = find_min_r_sub(*node);
 if(min_parent)
 { //Node is set with min value and the minimum node deleted
 node->data = min_parent->left->data;
 min_parent->left.reset();
 }
 else
 { //min_parent is null, so the the min value is the nodes right child.
 node->data = node->right->data;
 node->right.reset();
 }
}
template <class BST>
typename BinarySearchTree<BST>::node_t * BinarySearchTree<BST>::find_min_r_sub(const node_t &node) const
{
 node_t * parent = nullptr;
 node_t * current = node.right.get();
 while(current->left)
 /*- Loop traverses subtree as far left as possible.
 - Each iteration traverses one node.*/
 {
 parent = current;
 current = current->left.get();
 }
 return parent;
}
template <class BST>
void BinarySearchTree<BST>::remove_with_child(node_t * &parent, node_t * &current)
{
 if(!parent)
 { //node is root
 if(current->left)
 {
 root = std::move(current->left);
 }
 else
 {
 root = std::move(current->right);
 }
 }
 else if(current == parent->left.get())
 {
 if(current->left)
 {
 parent->left = std::move(current->left);
 }
 else
 {
 parent->left = std::move(current->right);
 }
 }
 else
 {
 if (current->left)
 {
 parent->right = std::move(current->left);
 }
 else
 {
 parent->right = std::move(current->right);
 }
 }
}
template <class BST>
void BinarySearchTree<BST>::remove_leaf(node_t * &parent, node_t * &current)
{
 if(!parent)
 { //node is root
 root.reset();
 }
 else if(current == parent->left.get())
 {
 parent->left.reset();
 }
 else
 {
 parent->right.reset();
 }
}
template <class BST>
bool BinarySearchTree<BST>::has_child(const node_t &node, const limb_t limb) const
{
 if(((node.left) && (limb == Left)) || ((node.right) && (limb == Right)))
 {
 return true;
 }
 return false;
}
template <class BST>
bool BinarySearchTree<BST>::is_empty(void) const
{
 if(tree_size == 0)
 {
 return true;
 }
 return false;
}
template <class BST>
bool BinarySearchTree<BST>::search(const BST &item) const
{
 node_t * current
 node_t * parent
 return (_search(item, parent, current));
}
template <class BST>
void BinarySearchTree<BST>::inorder() const
{
 inorder(root);
}
template <class BST>
void BinarySearchTree<BST>::_inorder(const node_p &node) const
{
 if(node)
 {
 if(node->left)
 {
 inorder(node->left);
 }
 std::cout<<" "<<node->data<<" ";
 if(node->right) 
 {
 inorder(node->right);
 }
 }
 else return;
}
template <class BST>
void BinarySearchTree<BST>::preorder(void) const
{
 preorder(root);
}
template <class BST>
void BinarySearchTree<BST>::_preorder(const node_p &node) const
{
 if(node)
 {
 std::cout<<" "<<node->data<<" ";
 if(node->left)
 {
 preorder(node->left);
 }
 if(node->right)
 {
 preorder(node->right);
 }
 }
 else return;
}
template <class BST>
void BinarySearchTree<BST>::postorder(void) const
{
 postorder(root);
}
template <class BST>
void BinarySearchTree<BST>::_postorder(const node_p &node) const
{
 if(node)
 {
 if(node->left) 
 {
 postorder(node->left);
 }
 if(node->right) 
 {
 postorder(node->right);
 }
 std::cout<<" "<<node->data<<" ";
 }
 else return;
}

• Memleak: You have a unique_ptr as a member variable therefore you are unable to copy this class. The following code should not be valid: BinarySearchTree<int> anotherTree = someAlreadyExistingTree;. Therefore you need to declare the copy constructor and the equal operator as private or to provide proper copy semantics for your class.
• Dirty Mike and the Boys: Awesome suggestion. I hadn't even thought of this, thanks!

Answer 1

There's quite a bit of code here so I haven't gone over it in great detail but the basics seem sound. Here's a few comments on things that jumped out at me at a quick skim though, some are pretty minor but are just suggestions for more idiomatic C++:

• This is a fairly major issue: generally the definitions of all templates need to be in a header file and not in a .cpp file. With your code as written, you will get linker errors if you try and use your BinarySearchTree class from another translation unit (another .cpp file). You can use explicit template instantiation to work around this if you know in advance the full set of instantiations you need but for a generic container class like this that may be instantiated with arbitrary types all your implementation should be in a header (you can separate it into a detail header for code organization purposes).
• It's conventional in C++ to use T for template type parameters when the meaning of the parameter is obvious (such as the contained type in a container). Naming your contained type template parameter BST seemed a slightly odd choice to me.
• Smart pointers are designed to manage ownership automatically and unique_ptrs default constructor initializes it to nullptr. It looks a little redundant to me to explicitly initialize your left and right node_ps with nullptr in the node_t constructor and your root in the BinarySearchTree constructor.
• Related to the above, it's redundant to call root.reset() in your BinarySearchTree destructor. Members of an object are automatically destroyed in the correct order, you should generally leave resource management up to types like unique_ptr that just do the right thing for you and only explicitly define a destructor for classes that manage resources.
• It's also redundant to set tree_size to 0 in your destructor - the object is going away so you are clearing a value you will never be able to access. I'd just delete your entire BinarySearchTree destructor as the implicitly generated destructor will be correct for this class.
• It's not idiomatic C++ to put void in the parameter list for functions that take no arguments (although it's permitted for backwards compatibility with C). Your default constructor and destructor (if you needed one) should just have empty argument lists.
• It's considered best practice in C++ to prefer pre-increment unless you need post-increment semantics (e.g. ++tree_size rather than tree_size++). This is because pre-increment can be more efficient for user defined types.
• You may want to consider taking 'sink' arguments (like the item parameter of your node_t constructor and of your insert() function by value and then std::move() them into their destinations. Alternatively you can provide two overloads, one taking a const T& argument and one taking a T&& which can be slightly more efficient by avoiding an extra move. Your insert() function doesn't handle movable types correctly and will not compile for move only types since it takes it's argument by const T& but attempts to std::move() them. Another option is to ignore move semantics for now and just accept copying (move semantics are a somewhat advanced C++ feature if you are trying to implement template classes that use them rather than to simply use them as a consumer of libraries).
• A handy tip when implementing templated container classes is to create helper classes for unit testing that record the number of copies / moves etc. This makes it easier to catch mistakes like your faulty insert() implementation by verifying that you are getting the number of moves and copies you expect.
• When designing container classes like this, consider using the same names and idioms in the interface as similar standard library types. For example, your search() function is generally named find() in similar standard library classes like std::set when it returns an iterator or count() when it returns the number of matching elements and insert() generally returns a pair<iterator, bool> or just an iterator indicating if the element was inserted and where it was inserted. It would also be good here to provide an iterator interface similar to standard library types, although it would require a fair bit of code to implement.

• Dirty Mike and the Boys: Thank you so much, these are the exact type of replies I was hoping to get. I don't know what I was think doing the template definitions in the cpp. I even thought while writing this that it was strange that you had to do the template definitions this way(good to know I just had no idea what I was doing). I like your input and am going to try to implement it tonight. I had considered adding an iterator but wanted to make sure this code was solid before committing to that much additional code.

Answer 2

A few stylistic details:

Take a look at this discussion on reserved names for C++. The POSIX standard actually reserves the _t suffix for itself. This is a very common notation in C, however portable code should avoid it.

Private functions and variables are very frequently prefixed with and underscore on other programming languages. In C++, this is not ideal. The _ prefix is reserved in a few cases (refer to the previous link). Inside your class, they are OK, but maybe consider not using this prefix in the future.

---

node_p name is little vague for the smart pointer type. NodePtr or NodePointer would be better. You can also try the using alias instead of the typedef (this was introduced with C++11):

using NodePtr = std::unique_ptr<node_t>;

It might read more naturally, since it follows the assignment syntax.

---

Your sentry comments are too big and verbose. Consider something more discreet, like this:

// ---- Class Variables: ----

Or no sentry comment at all. It is easy enough to read the declaration without them.

Also, your class declaration is not indented. You should give methods and variables one level of indentation like you would with any scope:

template <class BST>
class BinarySearchTree
{
public:
 bool insert(const BST &item);
 bool remove(const BST &item);
 bool search(const BST &item) const;
 ....
private:
 NodePtr root;
 ....
};

Personally, I think it makes more sense declaring the public interface of a class first. This is what users of the class will be interested on when they need to look at the declaration, so it seems logical to put it right at the beginning.

---

Starting with C++11, you can initialize member class data on declaration, so you could initialize three_size where it was declared:

int tree_size = 0;

root is a smart pointer, so it has default initialization to null, you don't need to explicitly initialize it.

If you do this, you can omit both the destructor and the constructor.

---

You have a few pointless comments in a few places, such as:

//Decrement tree size.
tree_size--;

And a few excessive parentheses in other places:

if(item == (current)->data)
// ^
// +-- Don't need this
if(((node.left) && (limb == Left)) || ((node.right) && (limb == Right)))
// ^ ^
// +-- Don't need this +-- Don't need this

Otherwise, the code is well written. You made use of nullptr, which is nice. NULL is C not C++.

One last thing you might want to look at it the Rule of Three to decide how you are going to handle copy and assignment. This is also an import aspect that should always be taken into consideration when writing a container-like class.

• Dirty Mike and the Boys: Thank you, I had hoped for input on style. I was very unsure of what to in a lot of cases. A lot of examples I found online would use C style or even camel case. I often struggle to find the right amount of commenting. I found those links very helpful as well. That first parentheses example was just sloppiness on my part, I can't even say why I would have written it like that.
• glampert: @DirtyMikeandtheBoys - If you're interested on modern C++ coding styles and standards, I recommend reading the LLVM and Google style guides.
• Dirty Mike and the Boys: Beautiful, thank you. I didn't know these existed.