Binary Search Tree Using Templates in C++

Question

I have made this BST using templates

Node.h

#ifndef NODE_H_INCLUDED
#define NODE_H_INCLUDED

template<typename T>
class Node
{
public:
    Node<T> *pLeft;
    Node<T> *pRight;
    T val;

    Node<T>(T val)
    {
        this->val = val;
        pLeft = pRight = nullptr;
    }

    // Node<T>(const Node<T>& src); -> to be implemented
    // Node& operator=(const Node&); -> to be implemented
};


#endif // NODE_H_INCLUDED

Tree.h

#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED

#include <iostream>
#include "Node.h"

template<typename T>
class Tree
{
    Node<T>* root;
    Node<T>* insert_at_sub(T i, Node<T>*);
    Node<T>* delete_at_sub(T i, Node<T>*);
    int countNodes(Node<T> *p);
    void print_sub(Node<T> *p);
    Node<T>* minValue(Node<T>*);
    Node<T>* maxValue(Node<T>*);
    Node<T>* get_last(Node<T>*);
    Node<T>* get_first(Node<T>*);
    int t_size = 0;

public:
    Tree ()
    {
        root = nullptr;
    }

    ~Tree()
    {
        delete root;
    }

    void add(T i)
    {
        ++t_size;

        root = insert_at_sub(i, root);
    }
    void print()
    {
        print_sub(root);
    };

    bool contain(T i)
    {
        return contain_sub(i, root);
    }
    bool contain_sub(T i, Node<T> *p);

    void destroy(T i)
    {
        if(contain(i))
            root = delete_at_sub(i, root);
        else
            return;
    }

    void showFirst();
    void showLast();

    int get_size()
    {
        return t_size;
    }

    int getNumberLeftNodes()
    {
        return countNodes(root->pLeft);
    }

    int getNumberRightNodes()
    {
        return countNodes(root->pRight);
    }
};

template<typename T>
int  Tree<T>::countNodes(Node<T> *p)
{
    static int nodes;

    if(!p)
        return 0;
    if (p->pLeft)
    {
        ++nodes;
        countNodes(p->pLeft);
    }
    if (p->pRight)
    {
        ++nodes;
        countNodes(p->pRight);
    }

    return nodes + 1;
}

template<typename T>
Node<T>* Tree<T>::insert_at_sub(T i, Node<T> *p)
{
    if( ! p )
        return new Node<T>(i);
    else if (i <= p->val)
        p->pLeft = insert_at_sub(i, p->pLeft);
    else if (i > p->val)
        p->pRight = insert_at_sub(i, p->pRight);

    return p;
}

template<typename T>
void Tree<T>::print_sub(Node<T> *p)
{
    if(p)
    {
        print_sub(p->pLeft);
        std::cout << p->val << std::endl;
        print_sub(p->pRight);
    }
}

template<typename T>
bool Tree<T>::contain_sub(T i, Node<T> *p)
{
    if (!p)
        return false;
    else if(i == p->val)
        return true;
    else if (i <= p->val)
        contain_sub(i, p->pLeft);
    else
        contain_sub(i, p->pRight);
}

template<typename T>

Node<T> *Tree<T>::minValue(Node<T> *p)
{
    Node<T> *current = p;

    while(current && current->pLeft)
        current = current->pLeft;

    return current;
}

template<typename T>
Node<T> *Tree<T>::maxValue(Node<T> *p)
{
    Node<T> *current = p;

    while(current && current->pRight)
        current = current->pRight;

    return current;
}

template<typename T>
void Tree<T>::showLast()
{
    Node<T> *last = maxValue(root);

    if(last)
        std::cout << last->val;
    else
        std::cout << "";
}

template<typename T>
void Tree<T>::showFirst()
{
    Node<T> *first = minValue(root);

    if(first)
        std::cout << first->val;
    else
        std::cout << "";
}


template<typename T>
Node<T>* Tree<T>::delete_at_sub(T i, Node<T>* p)
{
    if (i < p->val)
        p->pLeft = delete_at_sub(i, p->pLeft);
    else if (i > p->val)
        p->pRight = delete_at_sub(i, p->pRight);
    else if(i == p->val)
    {
        if ( ! p->pLeft)
        {
            Node<T> *temp = p->pRight;
            delete p;

            return temp;
        }
        else if ( ! p->pRight)
        {
            Node<T> *temp = p->pLeft;
            delete p;

            return temp;
        }

        Node<T> *temp = minValue(p->pRight);

        p->val = temp->val;

        p->pRight = delete_at_sub(p->val, p->pRight);
    }

    return p;
}

#endif // TREE_H_INCLUDED

main.cpp

#include <iostream>

#include "Tree.h"

using namespace std;

class Test
{
    string name;
public:
    Test () {}
    Test(string name_) : name(name_) {}

    friend ostream& operator<<(ostream& os, Test& t)
    {
        os << t.name;

        return os;
    }

    bool operator<(Test t);
    bool operator<=(Test t);
    bool operator>(Test t);
};

bool Test::operator<(Test t)
{
    return (name < t.name);
}

bool Test::operator<=(Test t)
{
    return (name <= t.name);
}

bool Test::operator>(Test t)
{
    return (name > t.name);
}

int main()
{
    Tree<int> tr;

/*
                       4
                    /      \
                   1        6
                 /  \      /  \
                0    2     5   9
                                 \
                                 89
                                /  \
                               12   222
                                 \
                                 32
                                /
                               22
*/

    tr.add(4);
    tr.add(6);
    tr.add(1);
    tr.add(9);
    tr.add(2);
    tr.add(0);
    tr.add(89);
    tr.add(12);
    tr.add(32);
    tr.add(5);
    tr.add(22);
    tr.add(222);


    //  tr.test();

   tr.showFirst();
   cout << endl;
   tr.showLast();
   cout << endl;

    Tree<string> bst;

    bst.add("Zanildo");
    bst.add("Helder");
    bst.add("Wilson");
    bst.add("Ady");
    bst.add("Adilson");
    bst.add("Patrick");


    bst.showFirst();
    cout << endl;
    bst.showLast();
    cout << endl;

    Tree<Test> test;

    test.add({"Jhonny"});
    test.add({"Bruno"});
    test.add({"Garry"});
    test.add({"Henry"});
    test.add({"Amber"});
    test.add({"Brandy"});
    test.add({"Danny"});
    test.add({"Cameron"});
    test.add({"Edla"});
    test.add({"Zenalda"});

    test.showFirst();
    cout << endl;
    test.showLast();
    cout << endl;

    //test.print();


    return 0;
}

I put all the Tree class functions implementation inside the header file because didn't want to put'em in a cpp file and having to add the explicit instantiation at the end of the file like this for example:

template class Tree<int>; // explicit instantiation

I also know I have to provide a copy constructor and an assignment operator for the Node class but I am still studying how to implement them correctly as this is my first time having the need to provide either of them. I have studied them before but while googling around came across the copy-swap idiom which is said to be the best approach so I have a few tabs open to study it and try to implement it. If anyone wish to give me a head start would be more than welcome.

An iterative BST is better for performance when the tree gets quite large but I have made the main functions for this BST recursively on purpose. I know how to implement those functions iteratively but not all of them yet. After I want to create this BST entirely iterative.

Besides all this, what can be said about my BST with template?

Answer 1

Make it explicit that it is a binary tree

Your class name is Tree, but there are many different types of trees. Make it clear that this is a binary tree, and name it BinaryTree.

Move class Node inside class Tree

Move the declaration of class Node inside that of class Tree, in the public section. This makes it clear that this Node is specific to the tree you are implementing, and avoids a potention conflict with other classes that might have nodes.

Consider for example that you might also have an implementation of a linked list, which also consists of nodes named Node. If you would want to use both your binary tree and your linked list in the same program, you would get a conflict.

Try to make your Tree look like other STL container classes

Have a look at what member functions STL containers define. The closest STL container to your binary tree is std::set. You don't have to add all the functionality of an STL container right away, just first consider renaming some of your member functions to match that of the STL. For example, instead of add() and destroy(), use insert() and erase(). Instead of get_size(), use size().

There are several benefits to this. First, for someone who is already familiar with other STL containers, it makes working with your Tree more intuitive. But that's not all: if you make it look enough like an STL container, then some of the STL algorithms might actually start to work on your Tree as well!

Move printing out of class Tree

Instead of having a print_sub() function that only prints to std::cout, consider writing instead a function that walks the tree and takes a function as one of its argument, so that it allows the caller to decide what to do with each visited node. For example:

template<typename T>
void Tree<T>::visit_subtree(const Node<T> *p, std::function<void(const T&)> func)
{
    if (p)
    {
        visit_subtree(p->pLeft, func);
        func(p->val);
        visit_subtree(p->pRight, func);
    }
}

template<typename T>
void Tree<T>::visit(std::function<void(const T&)> func)
{
    return visit_subtree(root, func);
}

Then you could call it like:

Tree<Test> test;
...
test.visit([](Test &val){std::cout << val << '\n';});

The advantage is that you can call it with any other function you like, so if you wanted to print it to std::cerr instead, or if you wanted to do something completely different with each element of the tree, you don't have to change your Tree's visit() function.

However, another approach is:

Implement iterators for your Tree

Try to implement an iterator class for your Tree, and provide begin() and end() member functions that return the appropriate iterators, to allow someone to loop over all the elements of the tree with a simple for-statement, like:

Tree<Test> test;
...
for (const auto &val: test)
    std::cout << val << '\n';

Read this question for some good references on how to implement an iterator yourself. It is a bit of work, but it makes using your class much easier. Once you have it, you also get many things for free. For example, instead of having to write your own minValue() function, once you have iterators you can just use std::min_element on an instance of a Tree class to get the smallest element.

Fix the memory leak in the destructor

Your destructor only deletes the root node, not any of its children.

Use const where appropriate

You should make arguments, variables, return values and whole member functions const whereever appropriate. For example, countNodes() does not modify the Node<T> that you give a pointer to as an argument, and it also doesn't change anything in class Tree itself. Therefore, you should declare it as:

int countNodes(const Node<T> *p) const;

The same goes for many other functions. Apart from catching potential errors and helping the compiler produce better optimized code, doing this will also allow these member functions to be called on const instances of class Tree.

Answer 2

A few extra points to the current answers:

• Tree will create a default copy constructor which will not behave as expected. As root is a raw pointer it will just do a shallow copy, assuming T is copiable (i.e. create a new pointer to the same data.) This will create unexpected behaviour if you copy the Tree and then modify one of the copies. As they both point to the same data both will be modified. You should either disable copying of Tree and Node, e.g. Tree(const Tree&) = delete; or write a custom copy that does a full deep copy of the data. The deep copy for Node would look something like this:

Node<T>(const Node<T>& src)
: val(src.val)
 {
    if(src.pLeft)
    {
        pLeft=*src.pLeft;
    }
    if(src.pRight)
    {
        pLeft=*src.pRight;
    }
 }

and something similar for Tree. NB I haven't done the copy-assignment here, you can either do something very similar to the copy constructor or implement a swap function and use that, see https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom.

• I would strongly recommend using smart pointers. This would prevent the memory leak in Node, and would implicitly prevent copying if you use unique_ptr.

• Your Tree allows duplicate elements, I'm not sure if this is intentional, but it has some not entirely obvious behaviour. add will perfectly happily add multiple of the same data, and destroy will only remove the first matching element. If this is intentional it should probably be documented. In most cases it is probably not necessary for a search tree to have duplicate elements.

• Consider adding ways to add/remove multiple elements at once. This is probably quite a common thing to do. The standard way would be a templated function taking a start and end iterator, that you can loop though.

• The performance of the tree is dependant on the order elements are added. This is not necessarily a problem, but is something to be aware of. If your tree is very unbalanced (e.g. the left nodes go a lot deeper than the right) some nodes will have to do many more checks to find than others. If you are interested in this you might want to look at self-balancing trees such as a red-black tree.

Answer 3

• There's no way to access the tree's nodes, so contain_sub is useless to clients.
• Even if it works, contain_sub doesn't return anything in two of its branches and looks gnarly.
• Use smart pointers or have a good reason not to.
• Don't copy items unless you're copying the tree itself; you're doing this a lot.
• Regarding iterators: remember that there are multiple ways to traverse a binary tree (pre/post/in/level order, and reverse).
• use_consistentNamingConventions (getNumberLeftNodes vs get_size).
• When would getNumberLeftNodes ever be useful to a client?
• Test your interface if you're going to write test code. 100% coverage is completely reasonable for a data structure.
• insert_at_sub could reduce to else returning the new node instead of having two returns
• "destroy" is semantically inaccurate for C++, it should be something like "erase".
• destroy is pretty inefficient and needs revising. Don't repeatedly traverse trees if you don't have to.

---

At a high level, why is this binary tree useful? Why not sort a vector or a list? Does this require fewer comparisons? Fewer pointer indirections? Fewer bytes allocated? It looks very slow at a cursory glance. If it's more optimal in some way than another data structure, write a test to demonstrate that.