C++ treeset implementation with templates

Question

I have to write a template for a treeset. The size of a leaf is 0. When the create_empty_set() is called it should make a leaf, when you add T data the leaf should become a branch and its value should be put in the left or right. No duplicates are allowed. Ill post the teacher's instructions here:

So, you'll need three classes: a supertype SortedTree and two subtypes named Branch and Leaf.

LinkedList nodes carried little integers with them. For our set, we want to do something better: we wish
the set to be able to contain any kind of values. The way to accomplish this is to make use of templates:
a TreeSet<T> contains values of type T.

Where do the set's elements reside exactly? Each Branch node contains exactly one T, while the leaves contain nothing:
they merely serve as "plugs" to fill the holes in the tree.

We don't want the T-values to be stored arbitrarily: there'd be no point in using a tree.
We want the values to be sorted. As mentioned above, each branch refers to two nodes (its child nodes) and has its own value.
A branch's value must be larger than all values stored in its left children but less than all values stored in its right children.
For example (leaves are not shown):

                            [BRANCH 8]
                             |      |
             +---------------+      +-------------------+
             |                                          |
        [BRANCH 4]                                  [BRANCH 11]
          |    |                                      |     |
    +-----+    +----+                           +-----+     +------+
    |               |                           |                  |
[BRANCH 1]      [BRANCH 7]                  [BRANCH 9]         [BRANCH 15]

Take the root node, i.e., the branch carrying 8. All values in its left node (1, 4, 7) are less than 8
and the values in the right children (9, 11, 15) are all greater than 8. The same rule is applicable on each branch in the tree.
Note that no duplicates are allowed: a set cannot contain the same value twice.

Im really confused and don't know how to proceed. Any push in to the right direction would be greatly appreciated.

[BRANCH] --> [BRANCH] --> [BRANCH] --> [LEAF]
   |            |            |
   |            |            +-----> [LEAF]
   |            |
   |            +-----> [BRANCH] --> [LEAF]
   |                       |
   |                       +-----> [LEAF]
   |
   +------> [BRANCH] --> [LEAF]
               |
               +-----> [BRANCH] --> [LEAF]
               |
               +-----> [LEAF]

This is what I already have.

#ifndef TREE_SET_H
#define TREE_SET_H
#include <memory> 

template<typename T>
class TreeSet
{
public: 
    TreeSet();
    virtual  int size();
     std::shared_ptr<TreeSet<T>> add(T data);
private:
    int _size;
    T value;
    std::shared_ptr<TreeSet<T>> left;
    std::shared_ptr<TreeSet<T>> right;
};

template<typename T>
class Leaf : public TreeSet<T> {
public: 
    Leaf();
private:
};

template<typename T>
class Branch : public TreeSet<T> {
public:
    Branch();
private:
};

template <typename T>
TreeSet<T>::TreeSet():_size(0) {
}

template<typename T>
Leaf<T>::Leaf() : TreeSet()
{
}

template<typename T>
Branch<T>::Branch() : TreeSet()
{
}

template<typename T>
std::shared_ptr<TreeSet<T>> create_empty_set()
{
    //return std::make_shared<TreeSet<T>>();
    return std::make_shared<Leaf<T>>();
}

template<typename T>
int TreeSet<T>::size() {
    return _size;
}

template<typename T>
std::shared_ptr<TreeSet<T>> TreeSet<T>::add(T data)
{
    return std::shared_ptr<TreeSet<T>>();
}`#endif

`
This is the add test

    #include "Catch.h"
#include "tree-set.h"
#include "util.h"

/*
    Add a method named "add" to the hierarchy. The method must take
    a value to be added to the set and return a new TreeSet that contains the element.
    The original tree must remain unchanged.
    Also update Branch's size().
*/


TEST_CASE("Adding element to TreeSet<int> yields new TreeSet<int>")
{
    const auto t1 = create_empty_set<int>();
    std::shared_ptr<TreeSet<int>> t2 = t1->add(5);    
}

TEST_CASE("Adding element to TreeSet<bool> yields new TreeSet<bool>")
{
    auto t1 = create_empty_set<bool>();
    std::shared_ptr<TreeSet<bool>> t2 = t1->add(true);
}

TEST_CASE("Adding single element increments size from 0 to 1")
{
    auto t1 = create_empty_set<bool>();
    auto t2 = t1->add(true);

    CHECK(t2->size() == 1);
}

TEST_CASE("Adding leaves the original TreeSet unchanged")
{
    auto t1 = create_empty_set<char>();
    auto t2 = t1->add('a');

    CHECK(t1->size() == 0);
}

TEST_CASE("Adding multiple elements increases size by 1 at each time")
{
    auto t = create_empty_set<int>();

    CHECK(t->size() == 0);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(1);
    CHECK(t->size() == 2);
    t = t->add(2);
    CHECK(t->size() == 3);
    t = t->add(3);
    CHECK(t->size() == 4);
}

TEST_CASE("Adding an element already in the set does not increment size")
{
    auto t = create_empty_set<int>();

    CHECK(t->size() == 0);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(0);
    CHECK(t->size() == 1);
    t = t->add(78);
    CHECK(t->size() == 2);
    t = t->add(78);
    CHECK(t->size() == 2);
}

this is another test

    /*
    Add a method size() to your hierarchy. For now, Branch's implementation of this method
    can return a dummy value.
*/


TEST_CASE("Size of an empty TreeSet<int> is zero")
{
    const auto t = create_empty_set<int>();

    CHECK(t->size() == 0);
}

TEST_CASE("Size of an empty TreeSet<bool> is zero")
{
    const auto t = create_empty_set<bool>();

    CHECK(t->size() == 0);
}

TEST_CASE("Size of an empty TreeSet<char> is zero")
{
    const auto t = create_empty_set<char>();

    CHECK(t->size() == 0);
}

TEST_CASE("TreeSet is a polymorphic type (i.e., it contains at least one virtual member)")
{
    const auto t = create_empty_set<int>();
    CHECK(is_leaf(*t));
}

This is the given util.h header

   #ifndef UTIL_H
#define UTIL_H

struct Foo
{
    bool operator <(const Foo& foo) const
    {
        return false;
    }
};

struct Bar
{
    int x;

    bool operator <(const Bar& bar) const
    {
        return x < bar.x;
    }
};

template<typename T, typename U>
bool has_dynamic_type(const U& x)
{
    return dynamic_cast<const T*>(&x) != nullptr;
}

template<typename T>
bool is_leaf(const TreeSet<T>& x)
{
    return has_dynamic_type<Leaf<T>>(x);
}

template<typename T>
bool is_branch(const TreeSet<T>& x)
{
    return has_dynamic_type<Branch<T>>(x);
}

#endif

Thanks in advance, Kelvijn

Answer 1

Your question is very vast. There are a few things I wish to point out. First, since your tree nodes are a template class, in order for the tree to be sorted you should be able to compare and sort the type. You can compare ints, you can compare strings (you must define a function to compare them or use strcmp) but you cannot really compare booleans for example. Unless you perhaps want to put falses to the left and trues to the right. Also when you make a tree of "Foo" where Foo is some class, you need to define a comparator for that class. Perhaps overload all or some of the operators == < > >= <=

Anyway sorting a tree also implies operations to keep it balanced. I recommend you start with Wikipedia https://en.wikipedia.org/wiki/Tree_sort and search other questions and answers.

Another important thing: In your code I would rename TreeSet into TreeNode. That's what it really is, what you wrote. The TreeSet is a set of TreeNode s. Just declare it as a pointer to the root node of the tree. And the Branch and Leaf do not deserve to be children classes really. It makes no sense at all. Just make a member function like (I am calling your TreeSet TreeNode for clarity)

bool TreeNode::isLeaf(){
    return !this.right && !this.left;
}

If this returns true then the node is a leaf otherwise it is a branch (or the root)...

When the create_empty_set() is called it should make a leaf, when you add T data the leaf should become a branch and its value should be put in the left or right.

Some clarity. Please make a proper distinction between the TreeSet and the TreeNode. Then to create_empty_set first call the constructor ( new TreeNode ) (this already creates an empty node) and next, you need to put it in the tree: run through the TreeSet (which is, I remind you, a pointer pointing at the root of your tree, the topmost node) through all the pointers of the nodes until you find your desired empty spot and place it where you like. If you are adding a unique value to a TreeSet, for example, trasverse the tree in some order (https://en.wikipedia.org/wiki/Depth-first_search for example in one of the 3 orders) and check if the data already exists: if it does, stop there, else add it to the proper node.