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

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.