# Binary Search Tree C++ Implementation

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) {
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.

-

## 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 :)

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 :)

-
A couple of things: 1. T& operator=(T) is perfectly reasonable; it's called the copy-and-swap idiom and it prevents code duplication and self-assignment bugs, among others. 2. Nothing in this class should be protected since it is not designed for subclassing (no virtual methods, destructor is public and nonvirtual). – ruds Sep 2 '14 at 0:38
1. Good point (placed a note in my answer), but there is no move constructor, so, it looked like a mess to me. 2. I won't agree to that. No virtual definitely does not mean no protected. I have written few templates that were enhanced later by more features (and variables) in another template - no virtual but still perfectly valid protected members. – firda Sep 2 '14 at 6:18
The class is not designed in any way to be a base class. Subclassing BST<T> would be like subclassing std::vector<T> -- it will all end in tears. Because the destructor is nonvirtual, you safely use the subclass polymorphically. Because there's no virtual methods to override, new functionality is best added through algorithms. See e.g. stackoverflow.com/questions/6806173/… – ruds Sep 2 '14 at 7:21
This is getting a debate, but ok: the destructor is non-virtual, so, it is not designed for polymorphism, but that is nothing against protected members. Sub-classing std::vector-like to create flat_set (sorted vector) is again perfectly valid scenairo and you can make the vector as protected base to disallow taking the pointer to the base. The possible polymorhic destruction may be the problem, not protected members. – firda Sep 2 '14 at 7:50
Please try to keep the edits down to a minimal now. Thanks! – Jamal Sep 2 '14 at 18:27

### 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 :-)

-
+1 for some good points. And I am very happy that - some days ago People used to indicate many beginner type problems like memory leak, deep copy, move semantics, memory allocation-deallocation etc in my snippet. I think I am improving! :P – Kaidul Islam Sep 1 '14 at 15:47
I'm kinda busy at the moment, so this is a bit superficial review. Stay tuned for more reviews by real C++ experts. Btw I just added a new note right at the top about your ::insert implementation. And yeah, hopefully we're all improving every day ;-) – janos Sep 1 '14 at 16:06
:) About the value vs. key, I would also prefer value in everywhere. I wrote it as key because I thought I would extend this class to implement STL map (though STL map requires a balanced BST e.g. RBT) – Kaidul Islam Sep 1 '14 at 16:16

# 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;

}


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.

-
+1 for your educative criticism. I am trying to correct all the points you've mentioned. – Kaidul Islam Sep 1 '14 at 17:00
This is one of the few cases were pointers are more appropriate than smart pointers. Pointers are used to implement of smart pointers and containers. In my opinion a BST is a container. Though you could make the argument to use std::unique_ptr but you wuold not use std::shared_ptr here as there is not shared ownership of each node. – Loki Astari Sep 2 '14 at 5:47
Yes, indeed std::unique_ptr is better but I wouldn't use it when the data members are public, as it is in his example. If those are made private then there is a whole different situation, and maybe it is acceptable to even use raw pointers, although my personal preference would still be to wrap it so I won't have to write a destructor. – Memleak Sep 2 '14 at 5:58
I have updated my answer to use unique_ptr as per Loki recommendation and moved the two declarations in a private section to avoid any confusions in the future. Thank you very much for the observation. – Memleak Sep 2 '14 at 6:49

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 ||.

-
Good points. 1. I would return true/false from remove (was / was not there). 2. I have left remove when I saw the uninitialized parent and if(curr->key == data) break. 3. Agree completely, looks odd. – firda Sep 2 '14 at 6:33