Creating a better BST

Question

I have created a BST like many others. I am curious to if there is a better way to write it. It seems pretty straight forward, but I feel like it can be improved on a bit.

//MRBST.h
#ifndef MRBST_H
#define MRBST_H
#include <iostream>
template <class T>
class MRBST {
private:
 struct treeNode
 {
 treeNode* left;
 treeNode* right;
 int data;
 };
 treeNode* root;
 int count;
public:
 void push(const T &);
 MRBST();
 bool search(const T &);
 void PrintPreorder();
 ~MRBST();
 bool empty() const;
 int numberOfNodes() const;
 void preorder(treeNode* pre);
};
template<class T>
MRBST<T>::MRBST()
{
 root = NULL;
 count = 0;
}
template<class T>
void MRBST<T>::push(const T & n)
{
 treeNode* d = new treeNode;
 treeNode* parent;
 d->data = n;
 d->left = NULL;
 d->right = NULL;
 parent = NULL;
 if(empty()) 
 {
 root = d;
 count++;
 }
 else
 {
 treeNode* current;
 current = root;
 while(current != NULL)
 {
 parent = current;
 if(d->data >= current->data)
 {
 current = current->right;
 }
 else
 {
 current = current->left;
 }
 if(d->data <= parent->data)
 {
 parent->left = d;
 }
 else
 {
 parent->right = d;
 }
 }
 count++;
 }
}
template<class T>
int MRBST<T>::numberOfNodes() const
{
 return count;
}
template<class T>
bool MRBST<T>::empty() const
{
 return root == NULL;
}
template<class T>
void MRBST<T>::PrintPreorder()
{
 preorder(root);
}
template<class T>
void MRBST<T>::preorder(treeNode* pre)
{
 if(pre != NULL)
 {
 std::cout << " " << pre->data << " ";
 if(pre->left)
 {
 preorder(pre->left);
 }
 if(pre->right)
 {
 preorder(pre->right);
 }
 }
}
template<class T>
MRBST<T>::~MRBST()
{
 delete root;
}
#endif

• ben rudgers: Some improvements are a matter of semantics...e.g. an optimal binary search tree might be an improvement if the intent is to search a stable data set frequently. See: ics.uci.edu/~dan/class/161/notes/6/OptBST.html and stackoverflow.com/questions/16987670/… and Knuth's TAoCP: Volume 3 - Sorting and Searching.

Answer 1

There are several improvements that can be done, starting from the class declaration:

• The class name is not very descriptive. MRBST could be an initialism for many things. BinarySearchTree is much better. Don't be afraid of using long names if they convey information more clearly.

• One thing doesn't make sense here: The class is a template class, but the data field of the treeNode is an int. If you are only storing ints, then the class doesn't have to be a template. You should however replace that int with T and make it generic.

• The naming convention of treeNode is a little unusual for types. This kind of camelCase notation is usually applied to variables. Types themselves are more commonly declared using CamelCase, fist letter uppercase.

• PrintPreorder() breaks your naming convention for methods. printPreorder() would be more consistent.

• Ordering of class data and member methods: I find more adequate placing public methods and data first, followed by protected methods/data and lastly anything private. This is convenient for readers of the class declaration, since they will be interested in the public interface most of the time.

• Order of the public fields: Place constructors first, followed by assignment/move operators, then the destructor and the rest after those. The fist thing you want to inspect when reading a class declaration is how the constructor(s), destructor and assignment are implemented, because that gives you hints about how the class lifetime is managed.

• Unnamed function parameters in push() and search(): You should always name function parameters in the header declaration because that's a form of code documentation.

• Remove excessive blank lines from the header file. There are some unexpected blank lines in there that serve no purpose. It looks untidy.

More aspect to improve in the implementation:

• Please don't use NULL in C++ code. Your compiler should be C++11 ready by now, so use nullptr.

• PrintPreorder() and preorder() should also be const methods since they don't mutate member state. Also the treeNode pointer that preorder() takes should be a const pointer. E.g.: const treeNode* pre.

• Currently, your class leaks memory. You are only deleting the root of the tree. All leaf nodes will leak. You need to recursively delete all nodes before deleting the root. The process is basically the same as how you did to print the tree.

There are probably more details that can be improved, as well as architectural improvements. Other reviews might want to expand on those.

• SilverSidewalkStew: Wow, there are a lot of things I have never thought of taking into perspective before. CamelCase or camelCase,blank lines, overall tidiness. Amazing, you are absolutely right. Just looking at the inconsistency of things like that just make me look unorganized. Thank you for showing me where I can improve because I will definitely take things like this into consideration every time I code now.

Answer 2

The code has a number of problems.

• push is badly broken. If current != NULL, the very first iteration replaces one of the parent's child with a newly created node. The whole subtree is therefore forgotten.

• The destructor is not deep. It only deletes a root node while leaving the rest of the tree intact, yet inaccessible. Memory leak it is.

• The

  d->data = n;
  d->left = NULL;
  d->right = NULL;
  

  part of push surely shall be a treeNode constructor.

• I don't see an implementation of search.

• As coded, preorder is PrintPreorder. It can't do anything but print. To be of any use, preorder shall take an action functor as a parameter.

• numberOfNodes in a container context traditionally is referred as size.

• SilverSidewalkStew: You're right, I really do have some kinks to work out. Thank you for your time and helping me out. This is all only going to make me better. Organization is key into writing better code and it is clear I often find myself unorganized.