0
\$\begingroup\$

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;
}
\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jan 27 '17 at 15:44
2
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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. \$\endgroup\$
    – Ash
    Jan 26 '17 at 21:35
  • \$\begingroup\$ 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. \$\endgroup\$
    – D. Jurcau
    Jan 27 '17 at 13:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.