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

• ruds: 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).
• user52292: 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.
• ruds: 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/…
• user52292: 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.
• Jamal: Please try to keep the edits down to a minimal now. Thanks!

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

• Kaidul Islam: +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
• janos: 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 ;-)
• Kaidul Islam: :) 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)

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.

• Loki Astari: 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.
• Memleak: 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: 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.

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

• user52292: 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.