Binary Search Tree implementation (OOP/classic pointers)

Question

In my implementation of a binary search tree, most functions take a pointer to a node (because of their recursive nature). So I found myself having to overload them, and the overloaded versions form somewhat of a public interface to the functionalities of the class. Is the design of the class good or bad? If it's bad please suggest an alternative.

(Please note: I haven't set the copy constructor and a copy assignment operator as deleted because I plan on writing a custom version of those very soon)

Another thing I'd like to take your input on is my use of classic pointers. Should I replace them with unique_ptrs?

Here's the header:

/////////BSTree.h//////////
#pragma once
#include <iostream>
#include <algorithm>
#include <vector>
#include <memory>
template <typename T>
struct node {
 T key;
 node<T>* left;
 node<T>* right;
};
template <typename T>
class BSTree {
public: //interface
 BSTree();
 ~BSTree();
 void insert(T item);
 void buildTree(std::vector<T> v);
 bool find(T item);
 T findMin();
 T findMax();
 void traverseInOrder();
 void traversePreOrder();
 void traversePostOrder();
 void destroyTree(); 
 void erase(T item);
 int height();
private: //implementation
 void insert(node<T>*& t, T item);
 node<T>* find(node<T>* t, T item);
 void traverseInOrder(node<T>* t);
 void traversePreOrder(node<T>* t);
 void traversePostOrder(node<T>* t);
 node<T>* findMin(node<T>* t);
 node<T>* findMax(node<T>* t);
 void destroyTree(node<T>*& t);
 bool erase(node<T>*& t, T item);
 int height(node<T>* t);
 node<T>* root_;
};
template <typename T>
BSTree<T>::BSTree()
{
 root_ = nullptr;
}
template <typename T>
BSTree<T>::~BSTree()
{
 destroyTree();
}
template <typename T>
void BSTree<T>::insert(node<T>*& t,T item)
{
 if (t == nullptr) //correct spot found or first insertion
 {
 t = new node<T>;
 t->key = item;
 t->left = nullptr;
 t->right = nullptr;
 }
 //look for correct spot in right or left subtree recursively
 else if (item > t->key)
 insert(t->right, item);
 else
 insert(t->left, item);
} //O(h) on average, O(n) worst case
template <typename T>
node<T>* BSTree<T>::find(node<T>* t, T item)
{
 if (t == nullptr) //empty tree
 return nullptr;
 else if (item == t->key) //item found
 return t;
 //item not found; look for right and left subtrees recursively
 else if (item < t->key)
 return find(t->left,item);
 else
 return find(t->right, item);
} //O(h) worst case
template <typename T>
node<T>* BSTree<T>::findMin(node<T>* t)
{
 node<T>* min = t;
 while (min->left != nullptr) //min node is the leftmost node
 min = min->left;
 return min;
} //O(h) worst case
template <typename T>
node<T>* BSTree<T>::findMax(node<T>* t)
{
 node<T>* max = t;
 while (max->right != nullptr) //max node is the rightmost node
 max = max->right;
 return max;
} //O(h) worst case
template <typename T>
void BSTree<T>::traverseInOrder(node<T>* t)
{ 
 if (t != nullptr)
 {
 traverseInOrder(t->left);
 std::cout << t->key << " ";
 traverseInOrder(t->right);
 }
} //O(n)
template <typename T>
void BSTree<T>::traversePreOrder(node<T>* t)
{ 
 if (t != nullptr)
 {
 std::cout << t->key << " ";
 traversePreOrder(t->left);
 traversePreOrder(t->right);
 }
} //O(n)
template <typename T>
void BSTree<T>::traversePostOrder(node<T>* t)
{ 
 if (t != nullptr)
 {
 traversePostOrder(t->left);
 traversePostOrder(t->right);
 std::cout << t->key << " ";
 }
} //runs in O(n)
template <typename T>
bool BSTree<T>::erase(node<T>*& t, T item)
{
 if (t == nullptr) //no deletion
 return 0;
 else if (item > t->key) //item not found; look in right or left subtrees
 erase(t->right, item);
 else if (item < t->key)
 erase(t->left, item);
 else //item found
 {
 if (t->left == nullptr && t->right == nullptr) //item is contained in a leaf node
 {
 delete t;
 t = nullptr;
 }
 else if (t->left == nullptr) //node has only a right child
 { //replace the node with its right child
 node<T>* del = t;
 t = t->right;
 delete del;
 }
 else if (t->right == nullptr) //node has only a left child
 { //replace the node with its left child
 node<T>* del = t;
 t = t->left;
 delete del;
 }
 else //node containing the item has both its children
 { //replace the node to delete with the min from the right subtree
 node<T>* temp = findMin(t->right);
 t->key = temp->key;
 erase(t->right, t->key);
 } //alternatively we can replace the node to delete with the max node from the left tree
 return 1; //item found and deleted
 }
} //requires O(h) time on average and O(n) worst case
template <class T>
int BSTree<T>::height(node<T>* t)
{
 if (t == nullptr) //empty tree has a height of 0
 return 0;
 else if (t->left == nullptr && t->right == nullptr) //leaf has height of 1
 return 1;
 else //calculate height recursively using the forumula:
 return (1 + std::max(height(t->left), height(t->right)));
} //runs in O(h)
template <typename T>
void BSTree<T>::destroyTree(node<T>*& t)
{ //destruction must occur from leafs all the way up to root
 if (t != nullptr)
 {
 destroyTree(t->left);
 destroyTree(t->right);
 delete t;
 t = nullptr;
 }
} //runs in O(n)
template <typename T>
void BSTree<T>::insert(T item)
{
 insert(root_, item);
}
template <typename T>
void BSTree<T>::buildTree(std::vector<T> v)
{
 for (auto item : v)
 insert(item);
} //this runs in O(m*h) on average and O(m*n) worst case (where m denotes vector length)
template <typename T>
bool BSTree<T>::find(T item)
{
 if (find(root_, item) != nullptr)
 return 1;
 return 0;
}
template <typename T>
T BSTree<T>::findMin()
{
 node<T>* min;
 min = findMin(root_);
 if (min != nullptr)
 return min->key;
 return std::numeric_limits<T>::max();
}
template <typename T>
T BSTree<T>::findMax()
{
 node<T>* max;
 max = findMax(root_);
 if (max != nullptr)
 return max->key;
 return std::numeric_limits<T>::min();
}
template <typename T>
void BSTree<T>::traverseInOrder()
{
 traverseInOrder(root_);
}
template <typename T>
void BSTree<T>::traversePreOrder()
{
 traversePreOrder(root_);
}
template <typename T>
void BSTree<T>::traversePostOrder()
{
 traversePostOrder(root_);
}
template <typename T>
void BSTree<T>::erase(T item)
{
 erase(root_, item);
}
template <class T>
int BSTree<T>::height()
{
 return height(root_);
}
template <typename T>
void BSTree<T>::destroyTree()
{
 destroyTree(root_);
}

Here's a demo:

#include <iostream>
#include <vector>
#include "BSTree.h"
int main() {
 BSTree<int> h;
 std::vector<int> v = {9,5,7,99,3};
 h.buildTree(v); //construct tree out of vector
 h.insert(-2); //atomic insertion
 h.insert(50);
 std::cout << "The height of the tree: " << h.height() << std::endl;
 std::cout << "Min element: " << h.findMin() << std::endl;
 std::cout << "Max element: " << h.findMax() << std::endl;
 h.traversePreOrder(); std::cout << std::endl;
 h.traversePostOrder(); std::cout << std::endl;
 h.traverseInOrder(); std::cout << "(this output is sorted)" << std::endl;
 //search returns a pointer to leaf, hence:
 if (h.find(5))
 std::cout << "5 is found" << std::endl;
 if (h.find(55)) //evaluates to false
 std::cout << "55 is found";
 h.erase(5);
 if (!h.find(5)) //notice '=='
 std::cout << "5 is no longer in tree";
 h.destroyTree();
 return 0;
}

• Joel Cornett: The one obvious disadvantage I see is that your search tree requires T to implement the less-than operator. Check out how the C++ standard library handles template parameters. Another problem is that your traversal functions don't really do anything useful. You should probably implement some variant of iterators or a visitor pattern for tree traversal.

Answer 1

Memory Management

If you don't have any special reason for using raw pointers, smart pointer can save you from a lot of headaches.

Passing Paramters

Passing non-trivial parameters (like std::vector) by value degrades performance.

API

Except for some homework assignments, one never uses a tree simply for printing values to the console. Your traverse methods should provide a way to iterate over the elements and do anything with each element.

A standard approach would be to provide iterators, but you could at least accept a callback and simply invoke it as you're traversing the elements.

If you're not exposing any public method that takes or returns a Node, I would hide the structure, it as an implementation detail.

• Ash: Thank you for your answer. 1- I'll try to use smart pointers instead. 2- I have changed the parameter to: const std::vector<T>& v. 3- I understood what you meant by the callback approach, but I'm not quite sure how to create an iterator for my structure. I'll look online and try to learn how first. 4- What do you mean by hiding the structure? Thanks again.
• D. Jurcau: For example, place the node structure inside your class or at least in a different namespace (now it's in the global one), so there's less chance that it'll interfere with another node class (name is quite common) that the source code might use/define.