Binary Search Tree implementation using templates

Question

I wrote this implementation using templates. It works fine and as expected. Just want to know if this can be improved. I have some specific questions too at the end. Please feel free to critique to your heart's content.

#include <iostream>
template <class T>
class Tree
{
 // Internal class which stores only Node related information.
 struct TreeNode
 {
 T data;
 TreeNode * left;
 TreeNode * right;
 TreeNode(T val):data(val),left(NULL),right(NULL)
 {
 }
 };
 TreeNode * root;
 void print(TreeNode*);
 void freeMemory(TreeNode*);
public:
 Tree();
 ~Tree();
 void insert(T);
 void print();
};
template <class T>
Tree<T>::Tree():root(NULL){}
template <class T>
Tree<T>::~Tree()
{
 freeMemory(root);
}
template <class T>
void Tree<T>::freeMemory(Tree::TreeNode *node)
{
 if (node==NULL)
 return;
 if (node->left)
 freeMemory(node->left);
 if (root->right)
 freeMemory(node->right);
 delete node;
}
template <class T>
//make it return value?
void Tree<T>::insert(T val)
{
 TreeNode * treeNode = NULL;
 try
 {
 treeNode = new TreeNode(val); // handle exception necessary?
 } catch (std::bad_alloc &exception)
 {
 std::cerr << "bad_alloc caught: " << exception.what() << std::endl;
 EXIT_FAILURE;
 }
 TreeNode *temp=NULL;
 TreeNode *prev=NULL;
 temp = root;
 while(temp)
 {
 prev = temp;
 if (temp->data < treeNode->data)
 temp = temp->right;
 else
 temp = temp->left;
 }
 if (prev==NULL)
 root = treeNode;
 else
 {
 if (prev->data<treeNode->data)
 prev->right = treeNode; // use setter function?
 else
 prev->left = treeNode;
 }
}
template <class T>
void Tree<T>::print(TreeNode *root)
{
 if (root==NULL)
 return ;
 print(root->left);
 std::cout << root->data << std::endl;
 print(root->right);
}
template <class T>
void Tree<T>::print()
{
 print(root);
}
int main()
{
 Tree<int> tree;
 tree.insert(14);
 tree.insert(12);
 tree.insert(6);
 tree.insert(17);
 tree.insert(8);
 tree.print();
}

1. Should I handle possible exceptions that can be thrown from new?

2. Is it good practice to have a TreeNode class as I've used? If not, how to make it better?

3. Should my insert return some value to indicate if insertion was successful?

4. Any other comments/suggestions?

• Loki Astari: Just as a note: std::set<T> is probably implemented as a tree (Its access characteristics defined in the standard would be the equivalent as if it was implemented by a balanced binary tree).

Answer 1

Exception handling

While it might make sense to handle the bad_alloc exception, the way you've done so is likely to lead to problems. The basic point of exception handling is that it decouples the point at which the exception is handled from the point at which it is generated. Right now, you've couple those by catching the bad_alloc immediately after the point at which it could be generated. Worse, you haven't handled it well at all. It looks like you intended to exit (stop execution), but in fact you only have EXIT_FAILURE, which is just a constant (typically 1). At least in theory, that's evaluated by the compiler as an expression which does nothing. In fact, there's a good chance the compiler will optimize such an expression way completely, so it does nothing.

Even assuming you corrected that so it exited the program correctly, code at that level (allocating a node) has no business deciding that bad_alloc should lead directly to exiting the program. In your test code that may make sense, but depending on how the search tree is being used, it make may sense to react to a bad_alloc in some other way. Leave that decision to the higher level code that can handle it more appropriately.

For example, it would make much more sense to handle it in main:

int main()
{ 
 try {
 Tree<int> tree;
 tree.insert(14);
 tree.insert(12);
 tree.insert(6);
 tree.insert(17);
 tree.insert(8);
 tree.print();
 }
 catch (std::exception const &e) { 
 std::cerr << e.what << "\n";
 }
}

With that in place, your code to allocate a node:

 TreeNode * treeNode = NULL;
 try
 {
 treeNode = new TreeNode(val); // handle exception necessary?
 } catch (std::bad_alloc &exception)
 {
 std::cerr << "bad_alloc caught: " << exception.what() << std::endl;
 EXIT_FAILURE;
 }

...becomes more like:

TreeNode *treeNode = new TreeNode(val);

...Only in really shouldn't be quite that either, because (as detailed below) you should really use unique_ptr instead of raw pointers.

bad_alloc specifics

bad_alloc, however, is kind of a special case, and I sometimes question whether it makes sense to handle it at all, at least in code intended for most typical desktop OSes. Memory allocation failure used to be pretty simple: you had N kilobytes of memory, and when/if that ran out, malloc returned NULL or new threw an exception.

Virtual memory changed that though. When you run out of memory, the OS swaps data to the swap file to make more room. In most typical cases, long before allocation has truly failed, the system will run slow enough for long enough that the user will kill the program long before the memory allocation actually fails. In fact, Linux actually kind of automates that process--it has an "OOM Killer" process that will kill processes to keep memory free so the system doesn't drag down to running too slowly. In most cases, that means your process will be killed without bad_alloc ever being thrown.

As such, it's quite debatable (at best) whether it makes sense to try to deal specifically with bad_alloc, at least in code for these systems.

For an interview, handling bad_alloc would depend. For embedded software, you typically do want to handle it. For desktop/server software, you may not want to, but if you don't you need to be prepared to explain why you don't.

"Raw" pointers

Most of what you've currently defined as pointers could really be instances of std::unique_ptr instead (again, at least assuming you're using a new enough compiler to support it). unique_ptr automates most of the "cleanup", so you could pretty much (probably completely) eliminate what you've currently implemented as freeMemory.

The downside of this is that a unique_ptr stores a deleter object that's used to clean up the pointee object when the unique_ptr goes out of scope. In the case of your binary tree, you'd at least normally assume that all the nodes in the tree to be deleted the same way. In that case, you probably either store no deleter object at all (and just use delete) or else store only one deleter for the entire tree, and internally use raw pointers. This can save quite a bit of storage space with (at worst) fairly minimal cost in code complexity.

Recursion pattern

Although I've already pointed out how it can probably be eliminated completely, let's assume for the moment that you're using raw pointers so you still need your freeMemory. If so, it can (IMO) be cleaned up a bit. Instead of checking for null pointers before you make the recursive call, just check for a null pointer once:

template <class T>
void Tree<T>::freeMemory(Tree::TreeNode *node)
{
 if (node==nullptr)
 return;
 freeMemory(node->left);
 freeMemory(node->right);
 delete node;
}

Each chain of recursive calls will stop when you reach a null pointer (thanks to the one if that remains). This reduces the complexity of this function pretty noticeably at essentially no cost¹.

Print

As @Jamal already pointed out, your print function doesn't modify the tree, so it should be const. I'd also prefer to see it allow the user to pass a specific stream to which the contents will be printed. In fact, it's at least worth considering overloading the stream insertion operator (operator<<) for your tree type, so you can insert a tree in a stream just like you would any other type:

Tree my_tree;
// code to insert data into tree goes here
std::cout << my_tree;

Alternative to Print

I'd at least consider whether you really want a Tree::print at all, or whether it's better to have the ability to walk the tree and apply essentially any function to all its nodes (with print as just one of those possibilities).

Return value from insert

I would say that yes, it's a good idea for insert to return a value indicating whether the insertion was successful. Your code is roughly analogous to std::set, which does return such a value, and I've used that return value quite a few times, so if I were going to use this, I'd probably make use of the same.

Iterators

If you were going to put this to real use, it would be preferable to be able to use it via a standard iterator interface. Alternatively, you might prefer to support a range interface (I'd probably prefer to use a range-based interface, anyway). This is probably getting beyond the scope of what you're currently thinking about though. You also quickly run into the fact that this provides pretty much a subset of what std::set already provides, so its practical use is probably limited in any case.

---

^{1. And in case you're wondering about the apparent contradiction of using nullptr in code that's only needed prior to C++11 (when nullptr was introduced), it's really pretty simple: nullptr is sufficiently trivial that a fair number of compilers supported it before they implemented rvalue references, which are crucial for unique_ptr. As such, even if you're using an older compiler that doesn't have unique_ptr there's a good chance it does have nullptr. It's even possible to define a nullptr class that works with C++03 compilers (a little Googling should turn up at least one).}

• Jamal: Would you say that the return type of insert() could vary (whatever the user should expect from it), or is returning something still preferred? I'm not opposed to either one, but my thinking with void was that the user doesn't need to know the outcome, especially if the structure will just be printed afterwards.
• Jerry Coffin: @Jamal: If you're using it for only this purpose, the return value isn't useful, but in more general use it can be. Yes, the type can vary--could be just a bool to indicate success, pointer to new node (null pointer on failure), or a pair<bool, pointer> to give both. The latter can indicate that a node was already present, and return a pointer to it in case the user wants to manipulate it somehow.
• Ian McGrath: @JerryCoffin Superb answer! I was trying using Unique pointer but when I insert for first time (if (prev==nullptr) root = treeNode;) I get error -- No viable overloaded = , and when I call print(root->left), I get error-- call to implicitly deleted copy constructor. I am really new with unqiue_ptrs, seems like I should read up more.
• Jamal: @IanMcGrath: It's okay. :-) Jerry is much better with data structures than I am (I'm also only a student), so listen to him most of all. See you again soon!
• Loki Astari: I would argue that containers and smart pointers are complimentary in memory management and should not use each other. So I would not be over hasty in using unique_ptr in the implementation of a container. But saying that. In this case I could see an argument for haveing a single unique_ptr in the tree object that holds the root. All the other members can be destroyed using the TreeNode destructor.

Answer 2

Should I handle possible exceptions that can be thrown from new?

Yes, if new fails, it'll throw std::bad_alloc, which should be caught and handled. Ideally, the tree should remain unchanged, but you may not be able to continue tree operations after this has occurred.

Is it good practice to have a TreeNode class as I've used? If not, how to make it better?

Yes, it is good practice, and your implementation is ideal. It's within the Tree class as private and even has its own constructor (optional, but usually preferred).

Should my insert return some value to indicate if insertion was successful?

It could just be void, at least if you want to keep things simple. If insert() fails, the function should just terminate. You could still return something, as long as it's something that the user may expect.

Any other comments/suggestions?

• print() should be const. If a member function is not supposed to modify any data members, making it const will ensure this. It also communicates the intent to others.

  template <class T>
  void Tree<T>::print(TreeNode *root) const
  {}
  

• insert()'s argument should be passed by const& in case T is a large type, which shouldn't be copied if it can be avoided. The argument itself is also not being modified.

  You also don't need to use exception-handling here. As mentioned above, you could simply return early if an item cannot be inserted. You would primarily need exception-handling if you were working with a returning function. If that can be avoided, then try to do so.

• Although not a critique, you should consider implementing this under C++11 and taking advantage of its features, such as nullptr, which should then replace NULL. Feel free to read about its other features and how it can improve your code.

• You should implemented other necessary functions, such as remove(), find(), and maybe also clear(). The user will likely expect these functions, and you'll especially need find() since this is, after all, a binary search tree.

• Ian McGrath: Thank you for this. The point about print and C++11 is acknowledged. Excellent points those. So for insert function, if new fails, I should just return?
• Jamal: @IanMcGrath: Yes, in general. But the calling code of this function usually wouldn't expect it to throw and thus may not be ready to handle it, so you should try to avoid that. Even then, the caller would catch, not the function. Again, you don't need it here.
• Ian McGrath: Thank you. Last question. Should I use smart pointers for left and right?
• Jamal: @IanMcGrath: You don't have to (and it would require C++11 anyway). I'm not 100% sure of their effectiveness here, but I've mostly seen raw pointers being used with data structures.
• Ian McGrath: I am ok with using C++11, this question is for job interview. I am to write a BST implementation.